View Single Post
Apr15-10, 04:22 PM
P: 14
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)


<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.
Phys.Org News Partner Science news on
Experts defend operational earthquake forecasting, counter critiques
EU urged to convert TV frequencies to mobile broadband
Sierra Nevada freshwater runoff could drop 26 percent by 2100