Seonglae ChoTuring Machine structures
math: M = (Q ,\Sigma, \Gamma, \delta, q_0, B, F)
- Q is finite set of control states
math: \Sigmais finite set of input symbols
math: \Gamma \supseteq \Sigmais a finite set of tape symbol
math: q_0 \in Qis the start (initial state)
math: B \in \Gammais the blank symbol
math: F \subseteq Qis the set of final (accepting) states
math: \delta : Q \times \Gamma → Q \times \Gamma \times\{L, R\}is transition function which describe finite control by control stage and symbol
Property
- Initially, the tape head is at the leftmost cell of the input right of B
- Since we have infinite table, so we cannot apply high level description for finite table
- since we have reusability we can call other subroutines by another Turing machine
- Unary data is easy to manipulate with Turing machines
- We need O(1) time & space to describe a state
- δ(q,X) = (p,Y,D) - overwrite X with Y in q
Based on the “scanned” symbol and the current state of the finite control, the macine does the following in one move
(a) Change its state
(b) Overwite a new symbol on the tape cell being currently scanned; it could rewrite the same symbol that was read
(c) Move the tape head left or right
The machine halts if there are no possible transitions to follow
Deterministic operation
Only one transition per symbol for each state
Function
computable function
Tape
We can simulate steps of a RAM-machine with a 3-tape TN in Cubic complexity steps. Vice-versa in steps.
