[Three components of a Universal Turing Machine] - A New Kind of Science: The NKS Forum

A New Kind of Science: The NKS Forum

Pages:1


Three components of a Universal Turing Machine

(Click here to view the original thread with full colors/images)


Posted by: Alex Vinokur

Article "Two components of a Universal Turing Machine "
at http://forum.wolframscience.com/sho...s=&threadid=467
should be rewritten as following.

-------------------------------------

Let TM be some Turing Machine,
let x be some input word for TM; x is a word in TM-alphabet.

Let UTM be some Universal Turing Machine.

To invoke UTM(TM, x) one should create input word y = t2u(UTM, TM, x);
y is a word in UTM-alphabet.
Function t2u may be named TM-to-UTM translator.

So, first stage of UTM invocation (for some input) is:
##########################################
### Stage-1. y = t2u(UTM, TM, x); x is a word in TM-alphabet, y is a
word in UTM-alphabet.
##########################################

Second stage is invocation of UTM itself:
##########################################
### Stage-2. z = UTM (y); y and z are words in UTM-alphabet.
##########################################

Third stage is translation of word z (which is in UTM-alphabet) to
word t in TM-alphabet : t = u2t (UTM, TM, z).
Function u2t may be named UTM-to-TM translator.
(Thanks to Pento for that point,
see http://groups.google.com/groups?sel...40134.58.127.12)
So, third stage of UTM invocation is:
##########################################
### Stage-3. t = u2t(UTM, TM, z); z is a word in UTM-alphabet, t is a
word in TM-alphabet.
##########################################


A practical question.
I would like to invoke Universal Turing Machines described
at http://mathworld.wolfram.com/Univer...ingMachine.html

Are there any TM-to-UTM and UTM-to-TM translators for those UTM's?


Posted by: Christina

Is there any possibility to find somewhere the operation of division with turing machine? and maybe a state diagram?
Thank you in advance.
Christina


Posted by: Jason Cawley

I put the TM division question to Matthew Szudzik, our TM instructor at the 2004 NKS summer program. He sent me this -


Before creating a Turing Machine that takes two numbers and performs division, one must decide on conventions for representing the input (a pair of numbers) and for representing the output (a single number).

Although the choice of conventions is arbitrary, that "arbitrary" choice can significantly affect the computation that is to be performed. In fact, I think that it would be an interesting NKS Summer School student project to find the smallest Turing machines that performs division under various conventions.

To simplify matters, let us create a Turing machine that divides by a fixed constant n, ignoring the remainder. Therefore, we only need to consider the single input x that is to be divided by n. Our Turing machine will only have two symbols (0 and 1), we will represent the input and output in unary notation, and we will consider the machine to have completed its computation when the head moves right of its initial position. These conventions are described in greater detail in the NKS Summer School 2004 Turing Machines Lecture (see the attached notebook).

Next, we need to decide what it means to "divide" x by n if the number x is not evenly divisible by n. The most common convention is to round down the fractional part of the division, and this is what Mathematica does when computing Quotient[x,n]. Alternatively, we could round up any fractional part of the division, as is done in the Mathematica computation Ceiling[x/n].

Now, using the conventions for representing Turing machines that are described on page 888 of a New Kind of Science. A (n+2)-state Turing machine QuotientTM[n] that computes Quotient[x,n] is given by -


 QuotientTM[n_] :=
  Flatten[{{{{1,0}->{n+2,0,1},{1,1}->{2,0,-1},{2,0}->{3,0,1},
{2,1}->{2,1,-1}}}, Table[{{i,0}->{n+2,0,1},{i,1}->{i+1,0,1}},
{i,3, n+1}],{{{n+2,0}->{1,1,-1},{n+2,1}->{n+2,1,1}}}},2]


You can perform computations with this machine using TMCompute, which is defined as follows.


 TMStep[r_,{s_,a_,n_}]:= 
  Which[ n<1,TMStep[r,{s,Prepend[a,0],n+1}],n>Length[a],
{s,a,n},True,{#1,ReplacePart[a,#2,n],n+#3}&@@Replace[
{s,a[[n]]},r]]

 TMCompute[rule_,init_]:= 
  FixedPointList[TMStep[rule,#]&,{1,init,Length[init]}]


So, for example, the computation for Quotient[8,3] is given by

TMCompute[QuotientTM[3],{0,1,1,1,1,1,1,1,1}] 

If you have the NKS Explorer Mathematica Kit (available at
http://www.wolframscience.com/nksx/nksxmk.html ), then you can make a graphic of this computation with -


 <<NKSExplorer`
 $ContextPath=Append[$ContextPath,"NKSExplorer`TuringMachines`"];

 Show[SingleTMPaddedGridGraphic[{#1,#2,Length[#2]-#3+1}&@@@TMCompute[QuotientTM[3],{0,1,1,1,1,1,1,1,1}]]]



You can also use NKS Explorer to make graphics of the Turing Machine rules. For example, the "rule icon" for QuotientTM[3] is

Show[BigTuringRuleGraphicxxx[QuotientTM[3]]] 

Note that a (n+2)-state Turing machine CeilingDivideTM[n] that computes Ceiling[x/n] for n>1 is given by -


 CeilingDivideTM[n_] :=
  Flatten[{{{{1,0}->{3,0,1},{1,1}->{2,1,-1},{2,0}->
{3,0,1},{2,1}->{2,0,-1}}},
  Table[{{i,0}->{i+1,0,1},{i,1}->{3,1,1}},
{i,3, n+1}],{{{n+2,0}->{n+2,1,1},{n+2,1}->{1,1,-1}}}},2]


Of course, other variations are also possible.

Matthew Szudzik


I hope this is useful.




Forum Sponsored by Wolfram Research

© 2004-2009 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. | Disclaimer
vB Easy Archive Final - Created by Xenon and modified/released by SkuZZy from the Job Openings