Turing Machine
"Turing first described the Turing machine in an article published in 1936, 'On Computable Numbers, with an Application to the Entscheidungsproblem', which appeared in Proceedings of the London Mathematical Society (Series 2, volume 42 (1936-37), pp. 230-265)." [1]
Configuration of Turing machine
Configuration of Turing machine is a characterization of Turing machine state and should be marked as: c=(q,x,i)
Where:
q: current state
x: current content of the tape
i: position of the actual tape cell
Calculation step
Calculation step of Turing machine is step which follow us from one configuration c=(q,x,i) to another configuration c´=(q´,y,j) and:
i: qss´q´R is an instruction of the program. x = usv |u|=i-1, y = us´v, j = i+1
i: qss´q´R is an instruction of the program. x = usv |u|=i-1, y = us´v, j = i-1
Sometimes we should say that step c=>c´ was realized by the application of the instruction i
(sgned c=i>c´) And instruction i is applicable in configuration c. About configuration c´we will say that is achievable from configuration c in one step.
Order of configurations c0, c1….cn will be called accusable order of configuration in Turing machine when ci-1 => ci for every i=1,2,….k
Configuration c, that has none applicable instruction is called dead configuration
If q0 is starting state then c = (q0,w,1) where w is tape is called starting configuration
If F is final state then c = (qf,x,i) where qf N� F is calles final configuration
Instruction of Turing machine
Turing machine instruction consist of five information’s represented by letters: q, s, s´, q´, D
q: current state
s: scanned symbol
s´: print symbol
q´: new state
D: one square move of the tape left or right
s0, 1, s0, 1, R this line skips over a series of 1s
s0, 0, s1, 1, R this line changes state to ’s1′ and the cell value to ‘1′ when the machine encounters an ‘0′ while it’s in state ’s0′
Turing thesis
“Every ‘function which would naturally be regarded as computable’ can be computed by a Turing machine.”
[1] Copeland, B.J., What is Turing Machine? Avaliable at: http://www.alanturing.net/