💨

What is Turing Machine

に公開
concept
history
turing
idea

What is Turing Machine

  • 1.Defination of Turing Machine
  • 2.Why a Turing Machine is essential?
  • 3.How Turing Machine works
  • 4.Chain of simulation approach

1. Defination of Turing Machine

Turing machine(TM) was invented by Alen Turing in 1936. It is a mathmatical model, simplest computer, and historical singnificance. TM has universal powers, meaning it can compute anything computable.

Alen Turing

2. Why a Turing Machine is essential?

TM has significant meaning to help you understand the limitation of computability. Althought it is an imaginary and theorical machine, you can know if any problems can computable or not with TM. Also, TM is the most simplest mathmatical computer, so you can apply TM to any models, meaning it dose not depend on OS, hardwares, and libraries.

3. How Turing machine works

1-Components

TM is surprisingly simple!
・Infinite tape: TM has tapes which is a divided cell, each cell has one symbol. It is like a laptop that has unlimited momery.
・Read/Write head: can read, write and move left/right or stay.
・Control unite: decide whether to read/write and a next situation based on the current situation.
・State dial: record the status of control unite.

2-Formal Turing machine definition

TM is mathmatically defined below
・ Alphabet Σ: types of characters that can be written on tape
Ex) Σ={A,C,G,T,⊔}
・State set Q: internal mode of the machine
Ex) Q={q0​,q1​,q2​,qaccept​,qreject​,qhalt​}
q0 = initial status(start)
q1, q2 = intermediate work state (calculation in progress)
qaccept = calculation succesfully done(Yes)
qreject = calculation fail because it is not satisfied with conditions(No)
qhalt = the processing has simply finished.
・Transition function δ: defined as δ(q,x)=(q′,x′,d′)
If the current state is q and the symbol on the tape is x, then proceed to the next state q′, write the symbol x′, and move in direction d′.

3-Simple example: lastTtoA machine

Goal: replace last 'T' with 'A'.
example outcome)
・CTCGTA → CTCGAA
・CGAT → CGAA
Basic algorithm
1.Start in q0, move right to end of string designated by ⊔.
2.Move to q1, scan left looking for a 'T' which must be last one.
3.When 'T' is found, replace with 'A' and halt the machine.

Trace of lastTtoA on input CTCGTA:
Step 1: q₀: [C] T C G T A (start, head at position 0)
Step 2: q₀: C [T] C G T A (read C, write C, move right)
Step 3: q₀: C T [C] G T A (read T, write T, move right)
Step 4: q₀: C T C [G] T A (read C, write C, move right)
Step 5: q₀: C T C G [T] A (read G, write G, move right)
Step 6: q₀: C T C G T [A] (read T, write T, move right)
Step 7: q₀: C T C G T A [⊔] (read A, write A, move right)
Step 8: q₁: C T C G T [A] ⊔ (read ⊔, write ⊔, move left)
Step 9: q₁: C T C G [T] A ⊔ (read A, write A, move left)
Step 10: qₕₐₗₜ: C T C G [A] A ⊔ (read T, write A, stay, halt)

(sample code)

class TM:
    def__init__(self, transitions, start_state='q0', blank='⊔'):
    self.transitions = transitions
    self.state = start_state
    self.blank = blank
    self.reset()

def reset(self):
    self.tape = []
    self.head = 0
    self.state = 'q0'
    self.steps = 0

def load_input(self, input_string):
    self.tape = list(input_string) + [self.blank]
    self.head = 0

last_t_to_a_transitions = {
       ('q0', 'C'): ('q0', 'C', 'R'),
    ('q0', 'T'): ('q0', 'T', 'R'),
    ('q0', 'G'): ('q0', 'G', 'R'),
    ('q0', 'A'): ('q0', 'A', 'R'),
    ('q0', '⊔'): ('q1', '⊔', 'L'),
    ('q1', 'C'): ('q1', 'C', 'L'),
    ('q1', 'G'): ('q1', 'G', 'L'),
    ('q1', 'A'): ('q1', 'A', 'L'),
    ('q1', 'T'): ('qhalt', 'A', 'S')
}

tm = TM(last_t_to_a_transitions)
print("Created lastTtoA machine")
print("Transitions_loaded:", len(last_t_to_a_transitions))

4-Explanation
The lastTtoA machine halts under these assumptions:
・input only contains symnols in {A, C, G, T}.
・input contains at least one 'T'.
If TM halts, then it may accept or reject, or simply halt.
!!PROBLEM!!
If the input is "CGGA" or "GGGG", what happends?
・The machine gets stuck in state q1.
・The machine will never reach a halting state.
・TM runs forever in that case, which is called "Infinite loop".

4.Chain of simulation approach

you can apply TM to any programming languages.
Ex) Liux can run any Java virtual machine and Java virtual machine can run any Java program.
Linx -> Java VM -> Java program
This is same as TM.

Discussion