Optimizing Turing Machine Functions: Finding the Minimum Cost and Enumeration

[mikestampone]

Hello smart people,

I am wondering if there is a process to convert a function to a Turing Machine. In other words, if I provide a list of input strings , and a corresponding output string for each input string, is there a way to find the minimum number of instructions to realize any function as a Turing Machine? Instructions can be either

<state,symbol,state_new,action> where action is new_symbol or move (left or right)

OR

<state,symbol,state_new,symbol_new,move> where move is left or right

If you could point me to resources, or provide the process in an algorithm I would be very happy. If this is a stupid question, or has already been solved in a previous post, I do apologize. Any help or direction is appreciated. Thanks.

 

[{~}]

I think a function (I assume you are speaking mathematically) could be a Turing machine who's "tape" is the real number line. Of course any finite interval on the number line would still correspond to infinite symbols and infinite tape. The tape is by definition discrete.

A function takes an independent variable or variables (your tape) and returns a dependent variable or variables (actions the Turing machine is to perform).

Input (starting position of the tape) -> action table (this is sort of the function part) -> output (action)

so let's say that your input is two pi and the function you want to represent is cos x (x is your input). You need to write a function table that tells the Turing machine how to behave when it encounters an input of 2 pi or any other symbol to get the right answer (One if we're talking about radians in this case).

The machine looks in the table under 2 pi it will see Left 2 pi Right 1 (when talking about a number line tape its handy to use left for decrements and right for increments).

Rather than calculating the dance steps of the Turing machine for every possible input value we define every cell in this table to be cos x - x.

For any function we should see that the table returns f(x) - x. The f(x) is our mathematical function, the value the reader moves to the right and x is our original input that we must subtract, move left, to offset.

If in the above example the table simply returned R cos x we would end up at cos x + x the wrong answer.

I hope this answers your question. If you do find resources out there on Turing machines or whatever could you post a link?

Good question BTW

 

[mikestampone]

Thanks for responding. A tape representing the natural numbers is interesting. I never thought of that. I am more concerned with dealing with symbols in general, and not the natural numbers or, certain real numbers, alone. I appreciate the response though. You provided a very detailed explanation of your concept.

>If you do find resources out there on Turing machines or whatever could you post a link?

Sure! These are my favorites.

http://plato.stanford.edu/entries/turing-machine/
http://plato.stanford.edu/archives/sum2003/entries/turing-machine/
http://www.maths.leeds.ac.uk/~awmorp...ne/turing.html

>Good question BTW
Thank you :)

 

[{~}]

I'm going to hazard you mean http://www.maths.leeds.ac.uk/~awmorp/turingmachine/turing.html
for that last link

Thanks

my question is, what exactly is your question?

Specifically can you define any function?

Consider each symbol to have an absolute address (pick some arbitrary panel of ribbon to be the orgin). Let's say some function defines the address of the output symbol f(S). S is the input symbol. The action in the action table will be right the out put address number left the input address number.

 

[mikestampone]

>my question is, what exactly is your question?

>Specifically can you define any function?

Alright, my question is, if I gave you a "function" (partial function?) , then how could you systematically find the minimum cost Turing Machine to solve that function. For example, when you count in binary...

**0*->**1*
**1*->*10*
*10*->*11*
*11*->100*

could you produce the Turing Machine which solved this problem with the minimum cost, if I provide specific cost values. For example...

computation_time_cost=5,
write_cost=10,
move_left_cost=20
move_right_cost=15

SO, to find the minimum cost machine, you would add the cost of performing an action, namely move or write, until the machine halted. The machine which returns the correct values and has the minimum cost, is the minimum cost Turing Machine. For counting, you move to the right to the end of the tape (*), then each value to the left is dependant on all the values to the right, because a 0 in the 2^1 position, doesn't mean that there is always going to be a value of 1 in the 2^0 position (for binary counting). The carry depends on the previous values, to the right.

I know how to count :) But how would you create a systematic way to apply a minimization algorithm to that and other things like multiplication, or exponents. I am thinking there must be a minimum solution for every problem, given the cost, because in school we learn multiple ways to solve a single problem, like multiplication.

Does that make sense?

 

[mikestampone]

Alright, maybe that is unnecessary. What if we wanted the Turing Machine with the smallest number of instructions, to implement whatever function? What if we also wanted to define the machine "head" at the start of the process, and the machine "head" at the end of the process? Could this be done? Any thoughts?

 

[mikestampone]

So...

Maybe I need to give an example of what I am looking for.

If I wanted to optimize for time, I would read the entire known tape left to right, and then write the sequence right to left.

Example

Given the function

000->000
011->110

The optimization for time, is

<s0,'0',s0,R>
<s0,'1',s1,L>
<s1,'0',s1,'1'>
<s1,'1',s2,R>
<s2,'1',s3,R>
<s3,'1',s3,'0'>

where you could replace the last line with

<s3,'1',s2,'0'>

and you would have the same machine. I want to know how to determine the "cost" of a machine, and an effective procedure to create a machine to solve a given task with the minimum "cost". For example, in circuits we have number of gates times computation time. From that definition of cost, we can minimize the circuit. I would like something similar for Turing Machines. Alright, well anyway, I also read that Turing Machines are enumerable. So...

What is machine 0? 1? ...
Is there a procedure to "list" all the Turing machines from 0-inf?

Answers to either questions are greatly appreciated. Thanks.