Turing Machines

In a previous post, I gave an informal explanation of the P=NP? problem. In that post, I described both deterministic and nondeterministic Turing machines. Now I’ve implemented the deterministic Turing machine in Python.

I also implemented a special deterministic Turing machine that decides whether a given positive integer is divisible by 4, just like the hypothetical Turing machine that I describe in my previous post.

I include a Bash script that tests that implementation. The script inputs every integer from 1 to 20 into the Turing machine program. The program passes every test.