I am new to turing machines, I am having problems with mapping a function to a turing maching that computes that particular function. for example:

  1. f(x) = 2x + 3 n>= 0
  2. MIN(x,y) leaves the smallest between x and y on the tape. e.g. x=2 y = 3 i.e. #aabaaa

I am not looking for a solution to the above but some kind of pattern i can use to solve these kind of particular problems quicker, in terms of transitions and what to have in mind before starting to solve.

  • $\begingroup$ Programming TMs is a pain. Why do you want to do that? That said, try formulating a "normal" program first, then translate to TM. (This question is very broad.) $\endgroup$ – Raphael May 18 '15 at 16:04
  • $\begingroup$ How is this supposed to be read: f(x) = 2x + 3 n>= 0 ? $\endgroup$ – babou May 18 '15 at 23:22
  • $\begingroup$ build primitives! subroutines! etc! lookup the concept of "assembly language", "machine codes", or "bytecodes" in java. the concept of language compilation is quite relevant. more on this topic (ruby TM compiler, examples, source code, object code, etc) $\endgroup$ – vzn May 19 '15 at 4:31
  • $\begingroup$ babou i meant x>=0, I can see doing sub-routines is the way to go $\endgroup$ – Plengo May 19 '15 at 6:59

Designing a Turing machine is pretty much like writing a program. You have to choose a representation for the data and a corresponding code (read * transitions*) to manipulate the data. Remember how we do arithmetics (addition, multiplication, quotient, ...) by manipulating in strange ways strings of symbols that represent numbers, whether in unary or positional representation, or even with Roman numerals.

The difficulty is generally that the means for data representation are pretty elementary: symbols on a tape. So you have to find ways to encode everything into that. Also the programming instructions are very simple. So you have to find a way (for complex machines) to decompose the problem into parts, and to assemble the coresponding machine parts. Pretty much what you do when you define functions and subprograms in usual programming.

You can make your life easier by using different sets of states for each subprogram. But basically people rarely design Turing machines, except for specific proofs. Then the problem is often how to combine into one several simpler machines that have been separately designed. You can find that in textbooks.

It can be amusing to find elegant solutions for simple problems. Like puzzles. You can add constraints. For example, you second question can be solved in several ways. Some use more tape than others.

Exercise: do long multiplication of two binary numbers, then two ternary numbers. Well, just think about it. Where would you store the multiplication table?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.