;---------------------------------------------------------------------------- ; utm.fsm ; David Boozer ; 28 April 2000 ; 1 November 2007 (modified, add documentation, rearrange code) ;---------------------------------------------------------------------------- ; Some notes on the UTM: ; ; A diagram of the initial state of the tape: ; +-+-+-+---+---+-+-+-+ ; |0|0|0|fsm|111|0|0|0| ; +-+-+-+---+---+-+-+-+ ; ; A diagram of the tape while the UTM is running: ; ; a b c d ; +-+-+-+---------------+----+---+---+-+-+-+ ; |x|x|1|00...0011...110|1110|fsm|111|x|x|x| ; +-+-+-+---------------+----+---+---+-+-+-+ ; ^ ^ ^ ^ ; Lend n buffer Rend ; ; Lend, buffer, and Rend are used as reference points to determine position ; fsm is a representation of the fsm of the Turing machine being simulated ; n is an index into the fsm ; ; The UTM is sandwitched between the left and right hand sides of the ; tape on which it is working. ; ; The fsm is generated by the following grammar: ; ; --> 100 ; --> ; --> e ; ; --> ; --> ; ; --> 100 (represents "1") ; --> 10 (represents "0") ; ; --> 1100 (represents "0R") ; --> 11000 (represents "1R") ; --> 110000 (represents "0L") ; --> 1100000 (represents "1L") ; ; e denotes the end of the fsm specification ; ; Switch on action: ; ; 0R => set b=0, shift UTM R one square, set n=n+d-2 ; 1R => set b=1, shift UTM R one square, set n=n+d-2 ; 0L => set c=0, shift UTM L one square, set n=n+a-2 ; 1L => set c=1, shift UTM L one square, set n=n+a-2 ; ;---------------------------------------------------------------------------- ; start 001 0 --> 001 0 R 001 1 --> 002 1 L ; create buffer 002 0 --> 003 0 L ;# 002 1 --> 010 0 L ;# mark fsm entry 003 0 --> 004 1 L ;# 003 1 --> 034 0 R ;# 004 0 --> 005 1 L ;# 004 1 --> 053 1 R ;# 005 0 --> 006 1 R ;# 005 1 --> 057 1 L ;# ; BEGIN: set n = (# of fsm entries) ; move R across buffer 006 0 --> 007 0 R 006 1 --> 006 1 R ; move R to 011 (fsm entry) 007 0 --> 007 0 R 007 1 --> 008 1 R 008 0 --> 007 0 R 008 1 --> 009 1 R 009 0 --> 002 0 L ; 11[0 => another fsm entry 009 1 --> 147 1 R ; 111[ => Lend ; move L to buffer 010 0 --> 010 0 L 010 1 --> 011 1 L 011 0 --> 010 0 L 011 1 --> 012 1 L ; move L across buffer 012 0 --> 013 0 L 012 1 --> 012 1 L ; move L across n, set n = n + 1 013 0 --> 014 1 R 013 1 --> 013 1 L ; move R across n 014 0 --> 006 0 R 014 1 --> 014 1 R ; END: set n = (# of fsm entries) +++ ; move L across Rend 015 0 --> 016 0 L 015 1 --> 015 1 L ; move L to buffer 016 0 --> 016 0 L 016 1 --> 017 1 L 017 0 --> 016 0 L 017 1 --> 018 1 L ; move L across buffer 018 0 --> 019 0 L 018 1 --> 018 1 L ; move L across n, increment n 019 0 --> 020 1 L 019 1 --> 019 1 L ; create Rend 020 0 --> 021 1 R ;# 020 1 --> 061 1 L ;# ; move R across n, erase n 021 0 --> 023 0 R 021 1 --> 021 0 R ;---------------------------------------------------------------------------- ; BEGIN: main loop ;---------------------------------------------------------------------------- ; move R across n 022 0 --> 023 0 R 022 1 --> 022 1 R ; move R across buffer 023 0 --> 024 0 R 023 1 --> 023 1 R ; move R to 011 024 0 --> 024 0 R 024 1 --> 025 1 R 025 0 --> 024 0 R 025 1 --> 026 1 L ; move L to buffer, unmark fsm entries 026 0 --> 027 0 L 026 1 --> 029 1 L 027 0 --> 028 0 L 027 1 --> 029 1 L 028 0 --> 028 0 L 028 1 --> 030 1 R 029 0 --> 026 0 L 029 1 --> 031 1 L 030 0 --> 026 1 L ;# 030 1 --> 065 1 L ;# ; BEGIN: loop to find nth fsm entry ; move L across buffer 031 0 --> 032 0 L 031 1 --> 031 1 L ; is n = 0? 032 0 --> 040 1 L ; n = 0 032 1 --> 033 1 L ; n > 0 ; move L across n, decrement n 033 0 --> 003 0 R 033 1 --> 033 1 L ; move R across n 034 0 --> 035 0 R 034 1 --> 034 1 R ; more R across buffer 035 0 --> 036 0 R 035 1 --> 035 1 R ; move R to 011 (fsm entry) 036 0 --> 036 0 R 036 1 --> 037 1 R 037 0 --> 036 0 R 037 1 --> 038 0 L ; mark fsm entry ; move L to buffer 038 0 --> 038 0 L 038 1 --> 039 1 L 039 0 --> 038 0 L 039 1 --> 031 1 L ; END: loop to find nth fsm entry ; set n = 2 040 0 --> 041 1 R ;# 040 1 --> 090 0 R ;# ; move R across n 041 0 --> 042 0 R 041 1 --> 041 1 R ; move R across buffer 042 0 --> 043 0 R 042 1 --> 042 1 R ; move R to 011 (fsm entry) 043 0 --> 043 0 R 043 1 --> 044 1 R 044 0 --> 043 0 R 044 1 --> 045 1 R ; 011[0 ; terminate fsm entry 045 0 --> 046 1 L ;# 011[1 045 1 --> 078 0 R ;# ; move L three squares 046 0 --> 047 0 L 046 1 --> 046 1 L ; ; continue continue stop stop ; xx0[1011100x x01[0011100x x11[1011100x xx0[0011100x ; 047 0 --> 048 0 L 047 1 --> 049 1 L 048 0 --> 127 0 R ; [00011100x => stop 048 1 --> 051 1 L ; [10011100x => continue 049 0 --> 050 0 L ; [01011100x => continue 049 1 --> 126 1 R ; [11011100x => stop 050 0 --> 052 0 L ; [001 050 1 --> 051 1 L ; [101 051 0 --> 050 0 L ; [010 051 1 --> 004 1 R ; 1[10 052 0 --> 053 0 R ; 0[00 052 1 --> 051 1 L ; [100 053 0 --> 053 0 R 053 1 --> 054 1 R ; BEGIN: loop to update n ; 10[01x or 10[1x 054 0 --> 054 0 R 054 1 --> 055 1 R ; 1001[x or 101[x 055 0 --> 056 1 R ; continue state specification, mark bit 055 1 --> 071 1 R ; end of state specification 056 0 --> 020 0 L ; One 056 1 --> 005 1 L ; Zero ; Zero ; move L to buffer 057 0 --> 057 0 L 057 1 --> 058 1 L 058 0 --> 057 0 L 058 1 --> 059 1 L ; move L across buffer 059 0 --> 060 0 L 059 1 --> 059 1 L ; move L across n 060 0 --> 065 0 R 060 1 --> 060 1 L ; One ; move L to buffer 061 0 --> 061 0 L 061 1 --> 062 1 L 062 0 --> 061 0 L 062 1 --> 063 1 L ; move L across buffer 063 0 --> 064 0 L 063 1 --> 063 1 L ; move L across n, set n = n + 1 064 0 --> 030 1 R 064 1 --> 064 1 L ; set n = 2*n 065 0 --> 068 0 R 065 1 --> 066 0 L 066 0 --> 067 1 R 066 1 --> 066 1 L 067 0 --> 065 1 R 067 1 --> 067 1 R ; move R across buffer 068 0 --> 069 0 R 068 1 --> 068 1 R ; move R to 011, unmark bit 069 0 --> 069 0 R 069 1 --> 070 1 R 070 0 --> 069 0 R 070 1 --> 054 0 R ; END: loop to update n ; determine action 071 0 --> 072 0 R ; 1100[ 071 1 --> 071 0 R ; 110[0 072 0 --> 073 0 R ; 11000[ 072 1 --> 075 1 L ; 1100[1 => action 0R 073 0 --> 074 0 R ; 110000[ 073 1 --> 081 1 L ; 11000[1 => action 1R 074 0 --> 112 0 R ; 1100000[ => action 1L 074 1 --> 109 1 R ; 1100001[ => action 0L ; action 0R ; move L to buffer, move L across buffer 075 0 --> 075 0 L 075 1 --> 076 1 L 076 0 --> 075 0 L 076 1 --> 077 1 L 077 0 --> 075 0 L 077 1 --> 078 1 L 078 0 --> 079 0 L ;# 078 1 --> 022 0 R ;# ; move L across n 079 0 --> 080 0 L 079 1 --> 079 1 L ; move L to Rend 080 0 --> 080 0 L 080 1 --> 087 0 R ; set old head = 0 ; action 1R ; move L to buffer, move L across buffer 081 0 --> 081 0 L 081 1 --> 082 1 L 082 0 --> 081 0 L 082 1 --> 083 1 L 083 0 --> 081 0 L 083 1 --> 084 1 L 084 0 --> 085 0 L ;# 084 1 --> 121 0 L ;# ; move L across n 085 0 --> 086 0 L 085 1 --> 085 1 L ; move L to Rend 086 0 --> 086 0 L 086 1 --> 087 1 R ; set old head = 1 ; 0R & 1R ; shift UTM R one square 087 0 --> 088 1 R ;# make Rend 087 1 --> 001 0 R ;# ; move R to n (shifting R one square) 088 0 --> 088 0 R 088 1 --> 089 0 R ; move R across n (shifting R one square) 089 0 --> 040 1 R 089 1 --> 089 1 R ; move R across buffer (shifting R one square) 090 0 --> 091 1 R 090 1 --> 090 1 R ; move R to Rend (shifting R one square) 091 0 --> 091 0 R 091 1 --> 092 0 R 092 0 --> 091 1 R 092 1 --> 093 1 R 093 0 --> 091 1 R 093 1 --> 094 1 R ; move one square R, create new Rend 094 0 --> 095 1 R 094 1 --> 095 1 R ; move one square to R, test state of new head 095 0 --> 096 0 L ; head = 0 095 1 --> 102 1 L ; head = 1 ; head = 0 ; move L across Rend 096 0 --> 097 0 L 096 1 --> 096 1 L ; more L to buffer 097 0 --> 097 0 L 097 1 --> 098 1 L 098 0 --> 097 0 L 098 1 --> 099 1 L 099 0 --> 097 0 L 099 1 --> 100 1 L ; move L to n 100 0 --> 101 0 L 100 1 --> 001 0 R ; move L across n, set n = n-2 101 0 --> 045 0 R 101 1 --> 101 1 L ; head = 1 ; move L across Rend 102 0 --> 103 0 L 102 1 --> 102 1 L ; move L to buffer 103 0 --> 103 0 L 103 1 --> 104 1 L 104 0 --> 103 0 L 104 1 --> 105 1 L 105 0 --> 103 0 L 105 1 --> 106 1 L ; move L to n 106 0 --> 107 0 L 106 1 --> 001 0 R ; move L across n, set n = n-1 107 0 --> 078 0 R 107 1 --> 107 1 L ; 0L ; move R to Rend 108 0 --> 108 0 R 108 1 --> 109 1 R ; action 0L 109 0 --> 108 0 R 109 1 --> 110 1 R 110 0 --> 108 0 R 110 1 --> 111 1 R ; set old head = 0 111 0 --> 116 0 L 111 1 --> 116 0 L ; action 1L ; move R to Rend 112 0 --> 112 0 R 112 1 --> 113 1 R 113 0 --> 112 0 R 113 1 --> 114 1 R 114 0 --> 112 0 R 114 1 --> 115 1 R ; set old head = 1 115 0 --> 116 1 L 115 1 --> 116 1 L ; 0L & 1L ; shift UTM L one bit ; move L across Rend (shifting L one bit) 116 0 --> 117 1 L 116 1 --> 116 1 L ; move L to buffer (shifting L one bit) 117 0 --> 117 0 L 117 1 --> 118 0 L 118 0 --> 117 1 L 118 1 --> 119 1 L 119 0 --> 117 1 L 119 1 --> 120 1 L ; move L to n (shifting L one bit) 120 0 --> 084 1 L 120 1 --> 001 0 R ; move L across n (shifting L one bit) 121 0 --> 122 1 L 121 1 --> 121 1 L ; move L to Lend (shifting L one bit) 122 0 --> 122 0 L 122 1 --> 123 0 L ; test state of new head, create new Lend 123 0 --> 124 1 R ; head = 0 123 1 --> 125 1 R ; head = 1 ; head = 0 ; move R to n, set n = n-2 124 0 --> 124 0 R 124 1 --> 078 0 R ; head = 1 ; move R to n, set n = n-1 125 0 --> 125 0 R 125 1 --> 022 0 R ; stop ; move R until 0 126 0 --> 128 0 R 126 1 --> 126 1 R ; move R until 1 127 0 --> 127 0 R 127 1 --> 128 0 R ; move R until 0 128 0 --> 129 0 R 128 1 --> 128 0 R ; determine action 129 0 --> 130 0 R 129 1 --> 132 0 L ; 0R 130 0 --> 131 0 R 130 1 --> 137 0 L ; 1R 131 0 --> 142 0 L ; 1L 131 1 --> 142 0 L ; 0L ; 0R, stop ; move L to buffer 132 0 --> 132 0 L 132 1 --> 133 0 L 133 0 --> 132 0 L 133 1 --> 134 0 L ; move L across buffer 134 0 --> 135 0 L 134 1 --> 134 0 L ; move L across n 135 0 --> 136 0 L 135 1 --> 135 0 L ; move L to Lend 136 0 --> 136 0 L 136 1 --> 000 0 R ; 1R, stop ; move L to buffer 137 0 --> 137 0 L 137 1 --> 138 0 L 138 0 --> 137 0 L 138 1 --> 139 0 L ; move L across buffer 139 0 --> 140 0 L 139 1 --> 139 0 L ; move L across n 140 0 --> 141 0 L 140 1 --> 140 0 L ; move L to Lend 141 0 --> 141 0 L 141 1 --> 000 1 R ; 0L & 1L, stop ; move L to buffer 142 0 --> 142 0 L 142 1 --> 143 0 L 143 0 --> 142 0 L 143 1 --> 144 0 L ; move L across buffer 144 0 --> 145 0 L 144 1 --> 144 0 L ; move L across n 145 0 --> 146 0 L 145 1 --> 145 0 L ; move L to Lend 146 0 --> 146 0 L 146 1 --> 000 0 L ;---------------------------------------------------------------------------- ;END: main loop ;---------------------------------------------------------------------------- ; (part of utm initializaiton) ; check status of head 147 0 --> 015 0 L ; head = 0 147 1 --> 148 1 L ; head = 1 ; move across Rend 148 0 --> 149 0 L 148 1 --> 148 1 L ; move L to buffer 149 0 --> 149 0 L 149 1 --> 150 1 L 150 0 --> 149 0 L 150 1 --> 151 1 L ; move L across buffer 151 0 --> 152 0 L 151 1 --> 151 1 L ; move L across n, increment n 152 0 --> 153 1 L 152 1 --> 152 1 L ; create Rend 153 0 --> 154 1 R ;# 153 1 --> 001 0 R ;# ; move R across n, erase n 154 0 --> 155 0 L 154 1 --> 154 0 R ; set n = 1 155 0 --> 022 1 R 155 1 --> 001 0 R