Conference rusure::math

4
1 B R 1
1 One R 2
2 One R 2
2 B L 2

ONE ONE ONE ONE ONE ONE ONE ONE ONE ONE B ONE ONE ONE ONE ONE ONE ONE ONE ONE 
ONE ONE ONE ONE ONE ONE ONE ONE ONE ONE B ONE ONE ONE ONE ONE ONE ONE ONE ONE 
ONE ONE ONE ONE ONE ONE ONE ONE ONE ONE B ONE ONE ONE ONE ONE ONE ONE ONE ONE 
ONE ONE ONE ONE ONE ONE ONE ONE ONE ONE B ONE ONE ONE ONE ONE ONE ONE ONE ONE 

4
1 B One 2
1 One B 2
2 B R 1
2 One R 1

The first machine doesn't do much.
The second machine is a bit-inverter.
This machine is an unary adder.
There is a bug.  Add two lines:
Before the loop to 100 put:
Instruction_Cycle_Count := 0;
After the READLN; put:
Instruction_Cycle_Count := Instruction_Cycle_Count + 1;
Tom

12
1 B R 1
1 One One 2
2 One R 2
2 B One 3
3 One R 3
3 B L 4
4 B L 4
4 One B 5
5 B L 5
5 One L 6
6 One L 6
6 B R 6

I made a nicer microturing.  It is in [TIGER]::STD:[janzen.public]turing.pas

It writes on the same line on VT100 instead of scrolling.  It prints out
the
next instruction and state for debugging purposes.  It halts for undefined
states.
Tom

There is now a language sensitive editor define file for turing.
It is at angora::std:[janzen.public]turing.lse for a limited time.
If you can't get it, ask.

when you get it, type to VMS 4
$ lsedit /init=your_device_is_mandatory:[your_directory]turing.lse

then in lse,
LSE> set language turing

then happily begin expanding.

Ask by mail for the current version of turing, an 80-space-long tape
turing machine for pedagogical purposes and debug data.
TOm

     I decided to pay tribute to the year that was by creating a
     Turing machine program to "write out" 1987.  The transition
     table is in the next reply.


     Some details:

     It has 32 states [can you do 1988 in fewer?].  Start it up
     in state 1 on a tape full of blanks.  On a two way infinite
     tape, the 796,374th transition will cause the tape head to
     move left from the starting tape cell, moving the tape head
     into state 30 scanning a blank.  That combination has no
     transition table entry, so the machine will halt.  402
     blanks to the right of the tape head, not counting the blank
     it is on, will be 1987 consecutive ones!  No tape cells to
     the right of the ones will have been scanned.  Happy Old Year!

     For a one-way infinite tape, you can let that last move
     "fall off" the left end of the tape, or add a new initial
     state 0 with transition table entry "0 B R 1" to start one
     square further to the right.  Either way the final contents
     will be 1987 ones.

     Dan

     In about a week I suppose I'll "document" it. :^)

59
 1 B   One  1
 1 One R    2
 2 B   One  2
 2 One R    3
 3 B   One  3
 3 One R    4
 4 B   R    5
 5 B   One  5
 5 One R    6
 6 B   One  6
 6 One R    7
 7 B   One  7
 7 One R    8
 8 B   One  8
 8 One R    9
 9 B   One  9
 9 One R   10
10 B   One 10
10 One R   11
11 B   One 11
11 One R   12
12 B   One 12
12 One R   13
13 B   One 14
14 B   R   15
14 One R   14
15 B   One 15
15 One L   16
16 B   L   16
16 One R   17
17 B   R   17
17 One R   18
18 B   One 19
18 One R   18
19 B   One 20
19 One R   19
20 B   One 21
20 One R   20
21 B   One 22
21 One R   21
22 B   One 23
22 One R   22
23 B   One 24
23 One R   23
24 B   L   25
24 One L   24
25 B   L   25
25 One B   26
26 B   L   27
27 B   L   28
27 One One 16
28 B   L   28
28 One B   29
29 B   L   30
30 One R   31
31 B   R   31
31 One R   32
32 B   L   14
32 One R   32

     The 1987 TM in reply .8 works as follows.  There are three
     sections, states 1-13, states 14-27, and states 28-32.

     The first section initializes the tape to have 3 ones, 1
     blank, and 9 ones, and ends scanning the rightmost of the 9
     ones in the first state of the second section.

     The second section is a subroutine.  If it begins scanning
     the rightmost of n ones, then it ends scanning the blank at
     the left of the ones, with the ones having been replaced
     with 6n+1 ones.  The 6n+1 ones start on the second cell
     after the "input" ones.  The state at the end is the first
     state of the third section.

     The third section moves left to the block of [initially 3]
     ones left by the first section.  It deletes the rightmost
     one, to mark that the "subroutine" second section has been
     run.  If any ones remain of that block the second section is
     "called" again.  If the last of the 3 ones was erased, the
     TM halts.

     After 3 calls to the n -> 6n+1 subroutine starting with n=9,
     there are 9 -> 55 -> 331 -> 1987 contiguous ones on the
     tape.

     The inner workings of the 6n+1 section mirror those of the
     TM as a whole.  First a single one is written to the right
     of the "input."  Then 6 more ones are written at the right
     of the growing section of ones and 1 of the "input" ones is
     erased.  If any of the original ones remain the "6 more"
     section is repeated, until the last "input" one is erased.

     Dan

     Re .7

>>   It has 32 states [can you do 1988 in fewer?].

     The following TM has 23 states (41 transition table entries)
     compared to 32 states (59 entries) for the 1987 TM.  It
     needs a two way infinite tape, as after 1,589,674
     transitions it is 12 cells to the left of its starting cell
     (this being as far left as it goes), in state 21 scanning a
     blank.  That combination has no transition table entry, so
     the TM will halt.  Far to the right are 1988 contiguous
     ones.  No tape cells to the right of the ones will have been
     scanned.  The rightmost one is 2640 cells to the right of
     the starting cell.

     The Computer Recreations section of the August 1984
     Scientific American magazine gave the transition table for a
     five state TM (found by Uwe Schult of Hamburg, West [?]
     Germany) that starts with a blank tape and ends with 501
     ones on the tape.  The TM's used there were different than
     used here -- at each transition the tape was written *and*
     the head moved, here only one of two may happen.  I "ported"
     Schult's machine; it is states 1-9 of the 1988 TM.   States
     10-12 and state 4 scanning a one delete the rightmost four
     ones.  The remaining states substitute 4 ones for each of
     the remaining 497 ones, finally halting with 1988 contiguous
     ones on the tape.  The 501 ones of the first section are not
     contiguous, but the embedded blanks only occur one at a
     time.  The leftmost of these ones can be found because it
     has two consecutive blanks to its left.

     Dan

     These little guys may have a reputation for being difficult
     to program, but it's not really true, building these TM's is
     relatively straightforward.

41
 1 B   One  6
 1 One B    6
 2 B   One  7
 2 One R    4
 3 B   One  8
 3 One B    8
 4 B   R    5
 4 One B   10
 5 B   One  9
 5 One R    1
 6 B   L    3
 6 One R    2
 7 One R    3
 8 B   R    2
 8 One L    1
 9 One L    3
10 B   L   10
10 One B   11
11 B   L   11
11 One B   12
12 B   L   12
12 One B   13
13 B   One 13
13 One R   14
14 B   One 14
14 One R   15
15 B   One 15
15 One R   16
16 B   One 17
17 B   L   18
17 One L   17
18 B   L   18
18 One B   19
19 B   L   20
20 B   L   21
20 One R   22
21 One R   22
22 B   R   22
22 One R   23
23 B   One 13
23 One R   23

     Define the function F on the positive integers by
     
          F(n) = the least positive integer k such that there
                 is a k state Turing machine which when started
                 on a blank tape will terminate with n ones
                 on the tape.
     
     Describe an algorithm for computing F, or else show that
     F is not Turing computable.
     
     Dan

     
>>    <<< Note 322.12 by LISP::DERAMO "Daniel V. {AITG,LISP,ZFC}:: D'Eramo" >>>
>>                   -< re "small" machines that "compute" n >-
>>
>>     Define the function F on the positive integers by
>>     
>>          F(n) = the least positive integer k such that there
>>                 is a k state Turing machine which when started
>>                 on a blank tape will terminate with n ones
>>                 on the tape.
>>     
>>     Describe an algorithm for computing F, or else show that
>>     F is not Turing computable.

     Suppose there was a Turing machine M1 with n1 states that
     computed F.  Use it as a subroutine to construct a machine
     M2 with n2 states that takes input n and returns the least
     nonnegative integer i such that F(i) > n.  For example, M2
     can use M1 to compute F(i) for i = 0, 1, 2, ... until it
     finds an i such that F(i) > n.  By the way, such an i must
     exist because there are only finitely many Turing machines
     with n or fewer states.
     
     Let J be a positive integer which will be specified later. 
     Construct a Turing machine M3 which acts as follows:  when
     started with a blank tape, it first writes out J ones.  This
     requires J states, ending up in state J+1 scanning to the
     right of the block of ones just written.  The next few
     states square the block of ones to the left of the call
     being scanned.  This squaring subroutine takes a fixed
     number of states I, which does not depend on J.  Finally,
     after the square of J is computed, an M2 subroutine (with n2
     states) uses this block of J^2 ones and computes the
     "M2" function described in the previous paragraph.
     
     From the description of M3 we see that is has J + I + n3
     states, or J + C for some fixed constant C which does not
     depend on J.  When started with a blank tape, M3 ends up
     having written "M2 of J^2" ones on the tape.  So M3 is a
     program with J + C states which writes out J^2 ones.  Now
     select J^2 so that J^2 > J + C.  For example, if C is 1000
     then J = 33 will do.  This can be done because C is fixed
     and does not depend on J.  Now "M2 of J^2" is a number so
     large that no machine with J^2 or fewer states can write out
     that many ones when started with a blank tape.  But M3 is a
     machine with J + C < J^2 states which does write out that
     many ones.  This is a contradiction, and so the assumption
     that a Turing machine M1 exists that computes F is false.
     
     This proof is essentially the same as the Scientific
     American article's proof of a few years ago that showed that
     the Busy Beaver function is not Turing computable.  The
     Busy Beaver function is defined as BB(n) = the greatest
     numbers of ones that an n state Turing machine will write on
     the tape when started with a blank tape.
     
     Dan