Image for post
Image for post

Turing Machines for Dummies

How is a Turing Machine different from a “regular” Computer

Practical Example of a Turing Machine

The Tape

Machine Alphabet

Reading and Moving the Tape

Comparison with a von Neumann Machine

Reading and Writing Data

Executing a Program

Image for post

How Does it Do Arithmetic?

Subtraction Example

Image for post
The state transitions are written such that what is on the left side of / is what you have read on the tape. The right side are the actions to perform. 1/0,R. Mean you read a 1. Then you write a 0 and more Right.
A  →111c1111  1/0,R
A  →111c1111  1/0,R
B 0→11c1111 1/1,R
B 01→1c1111 1/1,R
B 011→c1111 c/c,R
C 011c→1111 1/0,L
D 011→c0111 c/c,L
E 01→1c0111 1/1,L
E 0→11c0111 1/1,L
E →011c0111 0/0,R
A 0→11c0111 1/0,R
B 00→1c0111 1/1,R
B 000→c0111 c/c,R
C 000c→0111 0/0,R
C 000c0→111 1/0,L
D 000c→0011 0/0,L

Summary

Geek dad, living in Oslo, Norway with passion for UX, Julia programming, science, teaching, reading and writing.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store