Example: Turing transducer to map 0n1 _ 02n1, for n0
_ = {0,1} and _ = {0, 1, X, Y, b(blank)}; start state is 0.
0: if {0} print X, right_to 1; /* mark next '0' with 'X' */ if {Y} print 0, right_to 3; /* all '0's copied finish */ if {1} halt /* n=0 done */
1: while {0,Y} right; /* copy '0' as 'Y' at far right */ if {1,b} print Y, left_to 2
2: while {0,Y} left; /* rewind to 'X' */ if {X} print 0, right_to 0 /* restore 'X' to '0' and loop */
3: while {Y} print 0, right; /* replace 'Y' copies with '0' */ if {b} print 1, halt /* then halt */
With this machine for m0 and n>m 0ms00n-m1Ym _* 0mX0n-m-1Yms11 _* 0ms2X0n-m-1Ym+1b _* 0m+1s00n-(m+1)Ym+1b _* 0ns0Ynb _* 0n+1s3Yn-1b _* 0n0ns3b _ 02n1
Previous slide | Next slide | Back to first slide | View graphic version |