Turing machine for dummies

[enriquemesa2015]

Hello. I am studying turing machines. I know that a turing machine can read/write a symbol, move to left to right, and enter into a serie of states.

 

But i don't know how the transition function works.

 

I don't know how the turing machine can reference values when it only performs sequentialy operations. Please, give me an example explaining the addition of two binary numbers using it. Explain me also more about states.

 

Thanks.

[fiveworlds]

A turing machine is a theoretical machine using memory. The wiki says tape but you can use any memory whatsoever. The machine should be able to read and write to memory and perform calculations.

I bet you know how a full adder works.

 

An old example of tape memory was the cassette tape which was generally used to store music.

 

Edited July 24, 2016 by fiveworlds

[Strange]

Hello. I am studying turing machines. I know that a turing machine can read/write a symbol, move to left to right, and enter into a serie of states.

 

But i don't know how the transition function works.

 

I don't know how the turing machine can reference values when it only performs sequentialy operations. Please, give me an example explaining the addition of two binary numbers using it. Explain me also more about states.

 

Thanks.

 

 

I'm not sure what bit you are having trouble with.

 

I assume by "transition function" you mean what it decides to do in any given state? That is determined by the value on the tape, the internal state register(s) and the current instruction in the table. The table says what to do in that specific configuration (move, print a value, etc).

 

Arbitrary values would have to be read sequentially, one digit at a time (which would be used to modify a state register).

 

The Wikipedia description is pretty good: https://en.wikipedia.org/wiki/Turing_machine

And they have some examples: https://en.wikipedia.org/wiki/Turing_machine_examples

And an example of adder here: https://www.cs.virginia.edu/~evans/cs150/classes/class37/lecture37.pdf

There are various simulated Turing Machines you can play with online, which might help you get to grips with it. For example:

http://morphett.info/turing/turing.html

https://turingmachinesimulator.com

http://www.turing.org.uk/book/update/tmjavar.html

[ydoaPs]

An old example of tape memory

...not that old :'(