CODEWITHSUNDEEP
turing-machinescomputation-theory
Straightfw
Straightfw

Reputation: 2211

Turing machine and coming up with an idea

I read many things about the Turing machine and understand how it works but what I can't get the grasp of (and what none of the books seem to try to teach) is how should I approach a problem I am given to solve? I mean: checking if a word is a palindrome, for example, consists of 11 states in the book I'm learning from. For my current state of knowledge, just sitting over an empty sheet of paper and coming up with all these states seems next to impossible, to say the least. When I try to do something like this, I get stuck immediately since I don't know what should I do to make these states work somehow "together". I don't have such problems when programming but here, I just can't figure out how I should approach something consisting of some n-teen states. Could you please point me some direction to learn about it?

Upvotes: 1

Views: 145

Answers (1)

Andrea Asperti
Andrea Asperti

Reputation: 1003

Turing Machines are an architectural model, not very far from a Von Neumann machine. So, it is a very low-level model of computation and the best way of approaching the problem of programming with them, is by the same technique we would use for traditional hardware, namely via abstractions.

It is believed that Turing Machines are not compositional, but this is not really true. It is not difficult to combine the transition function of Turing machines realizing sequential composition, conditionals and loops. Then, starting from a small library of basic machines perfoming character comparison, character swapping, and similar operations you may build up very complex programs.

We used this technique to write a Universal Turing Machine, and certify its correctness in the Matita Proof Assistant (a system similar to Coq). The reference is:

Asperti, Ricciotti "A formalization of multi tapes Turing Machines", TCS 603, 2015.

Upvotes: 0

Related Questions