Turing Machine
matsuda@symbolics.jp
(cf. "Compuer Science with Mathematica", Roman E. Maeder)
Background Idea of Turing Machine
cf. http://en.wikipedia.org/wiki/Turing_machine Automatic Machine (Alan Turing 1936)
Hypothetical device representing a computing machine
“Intelligent Machinerry” (1945 Essay)
Turing Machine cosists of the following device and the functions (1)an infinite tape
(2)a head which read/writes a symbol on the tape and can move one position (3)a state register which memorize the current position of the head on the tape (4)a rule table(program) which decides the next action to the tape head The original idea comes from the followin fundamental question: [Hilbert’s tenth question of 1900]
10. Determination of the solvability of a Diophantine equation. Given a Diophantine equation with any number of unknown quantities and with rational integral coefficients: To devise a process according to which it can be determined in a finite number of operations whether the equation is solvable in rational integers. The Entscheidungsproblem [decision problem for first- order logic] is solved when we know a procedure that allows for any given logical expression to decide by finitely many operations its validity or satisfiability ... The Entscheidungsproblem must be considered the main problem of mathematical logic.
—quoted, with this translation and the original German, in Dershowitz and Gurevich, 2008
Allan Turing proofed this question with a negative answer and invented a Turing Machine as a secondary effect.
“The theory of computation has traditionally been studied almost entirely in the abstract, as a topic in pure mathematics. This is to miss the point of it. Computers are physical objects, and computations are physical processes. What computers can or cannot compute is determined by the laws of physics alone, and not by pure mathematics”
– David Deutsch (one of top runners in quantum computing ) Q.What is computation?
A. Proof not with indcutive method but with constuctive method (Turing Machine) by using the following rough(not in Turing Machine but here) computing parts:
zero successor while compose ...
Lego Turing Machine
Automatic Computing Engine (ACE) designed by Alan Turing(1946), finished on 1954.
Preparing a Tape
Assuming a infinite tape. The function tape creates a tape which contents is given by list and which head is specified by offset. The symbol indicates a blank.
cf. Array[t,6]-->{tape[...][1], tape[...][2],tape[...][3]....}
updating the tape
cf. /: TagSetDelayed define ‘module’ operation
stack example
finding a non-blank position
new tape
For example newTape[1,b] supposes p0 is 1, so the offset of this tape will be 0(p0-1).
Defining a turing machine wih configuration and instruction
initial configuration
The left most 1 of config indicates the state number and the right most 1 indicates the positin of the tape.
Instructions
Example. Instruction set for subtracting one from the current value. In the initial step, the state is 1 and the current value is b then moves the head to the right and changes the status to 2 (the first instruction).
{1,b}!{b,r,2} {2,m}!{m,r,2} {2,b}!{b,l,3} {3,m}!{b,l,4} {3,b}!{b,s,0} {4,m}!{m,l,4} {4,b}!{b,s,0}
updating a configuration
3 - 1
computes 3 - 1. Three marks will be decresed two ones.
config[1,< b m m m b b ...>,1] config[2,< b m m m b b ...>,2] config[2,< b m m m b b ...>,3] config[2,< b m m m b b ...>,4] config[2,< b m m m b b ...>,5] config[3,< b m m m b b ...>,4]
config[4,< b m m b b b ...>,3] config[4,< b m m b b b ...>,2] config[4,< b m m b b b ...>,1] config[0,< b m m b b b ...>,1] config[0,< b m m b b b ...>,1]
add
defining a run
1+3
a sub b, supposing a > b
3 - 2
Assembler for Turing Machine
Following controls are available: right, while, skip[n], skip[-n], shifleft[n], eat1[n], copy[n,m]
How to compose number of instructions
Should reloate for sates. like allocating absolute address for relative address in compiler.
First example is right. This comand consists of two instuctions for moving the head one step to the right accoring to the current valuse b and m. Note the target state should be 0 because correct value will be assigned when command composition.
right; right;
in the first right, the offset is 0, transition is 1 to 2. in the second right, the offset is 1 and the transition is 0.
compose
automatically to comose several commands lile compose[right, right]. cf. tutorial/FlatAndOrderlessFunctions
while
other commans
zero
successor
Created with Wolfram Mathematica 8.0
