[Solved]: What is a standard way to construct a turing machine for any function to compute

Problem Detail: 

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.

Asked By : Plengo

Answered By : babou

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?

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/42708