;---------------------------------------------------------------------------- ; utm.fsm ; David Boozer ; 28 April 2000 ; 01 November 2007 (modified, add documentation, rearrange code) ; 25 January 2009 (modified, change documentation) ;---------------------------------------------------------------------------- ; Some notes on the UTM: ; ; The finite-state machine (fsm) of the Turing machine to be simulated is ; encoded as a binary number, which is described by the following grammar: ; ; --> ; --> ; --> e ; ; --> ; --> ; ; --> 100 (represents "1") ; --> 10 (represents "0") ; ; --> 1100 (represents "0R") ; --> 11000 (represents "1R") ; --> 110000 (represents "0L") ; --> 1100000 (represents "1L") ; ; Here "e" denotes the end of the fsm specification. ; ; The initial tape state looks like this: ; ; +---+---+----------------+ ; |fsm|111| simulated tape | ; +---+---+----------------+ ; ; In general, the Universal Turing Macine (UTM) is sandwiched between the ; left and right hand sides of the simulated tape, and the tape looks like ; this: ; ; a b c d ; +-+-+-+---------------+----+---+---+-+-+-+ ; |x|x|1|00...0011...110|1110|fsm|111|x|x|x| ; +-+-+-+---------------+----+---+---+-+-+-+ ; ^ ^ ^ ^ ; Lend n buffer Rend ; ; The UTM uses "Lend", "buffer", and "Rend" as reference points to determine ; the position of the head; "fsm" is a binary coding of the finite-state ; machine of the Turing machine being simulated; "n" is an index into the ; finite state machine. ; ; 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 ; ; The following terminology is used: ; ; To "mark" an fsm entry means to erase the second 1 in the action field ; for that entry. For example: ; ; 1100 <-- unmarked 0R entry ; 1000 <-- marked 0R entry ; ; To "terminate" an fsm entry means to add a third one in the action field ; for that entry. For example: ; ; 1100 <-- unterminated 0R entry ; 1110 <-- terminated 0R entry ; ; To "mark" a bit means to add a second 1 to to the bit. For example: ; ; 10 <-- unmarked "0" ; 11 <-- marked "0" ; 100 <-- unmarked "1" ; 110 <-- marked "1" ; ;---------------------------------------------------------------------------- create_buffer: 000 0 --> 000 0 R 000 1 --> 001 1 L 001 0 --> 002 0 L 001 1 --> nop 002 0 --> 003 1 L 002 1 --> nop 003 0 --> 004 1 L 003 1 --> nop 004 0 --> jmp 1 R > set_n_to_num_fsm_entries 004 1 --> nop ;---------------------------------------------------------------------------- set_n_to_num_fsm_entries: ; move R across buffer 000 0 --> 001 0 R 000 1 --> 000 1 R ; move R to 011 (fsm entry) 001 0 --> 001 0 R 001 1 --> 002 1 R 002 0 --> 001 0 R 002 1 --> 003 1 R 003 0 --> 009 0 L ; 11[0 => another fsm entry 003 1 --> 010 1 R ; 111[ => Lend ; move L to buffer 004 0 --> 004 0 L 004 1 --> 005 1 L 005 0 --> 004 0 L 005 1 --> 006 1 L ; move L across buffer 006 0 --> 007 0 L 006 1 --> 006 1 L ; move L across n, increment n 007 0 --> 008 1 R 007 1 --> 007 1 L ; move R across n 008 0 --> 000 0 R 008 1 --> 008 1 R 009 0 --> nop 009 1 --> 004 0 L ; mark fsm entry (should reorder this) ; check status of head 010 0 --> jmp 0 L > initialize_for_head_0 010 1 --> jmp 1 L > initialize_for_head_1 ;---------------------------------------------------------------------------- initialize_for_head_0: ; move L across Rend 000 0 --> 001 0 L 000 1 --> 000 1 L ; move L to buffer 001 0 --> 001 0 L 001 1 --> 002 1 L 002 0 --> 001 0 L 002 1 --> 003 1 L ; move L across buffer 003 0 --> 004 0 L 003 1 --> 003 1 L ; move L across n, increment n 004 0 --> 005 1 L 004 1 --> 004 1 L ; create Lend 005 0 --> 006 1 R 005 1 --> nop ; move R across n, set n = 0 006 0 --> jmp 0 R > main_loop+1 006 1 --> 006 0 R ;---------------------------------------------------------------------------- initialize_for_head_1: ; move across Rend 000 0 --> 001 0 L 000 1 --> 000 1 L ; move L to buffer 001 0 --> 001 0 L 001 1 --> 002 1 L 002 0 --> 001 0 L 002 1 --> 003 1 L ; move L across buffer 003 0 --> 004 0 L 003 1 --> 003 1 L ; move L across n, increment n 004 0 --> 005 1 L 004 1 --> 004 1 L ; create Lend 005 0 --> 006 1 R 005 1 --> nop ; move R across n, set n = 0 006 0 --> 007 0 L 006 1 --> 006 0 R ; set n = 1 007 0 --> jmp 1 R > main_loop 007 1 --> nop ;---------------------------------------------------------------------------- main_loop: ; start with head to the left of n, fsm entries marked ; move R across n 000 0 --> 001 0 R 000 1 --> 000 1 R ; move R across buffer 001 0 --> 002 0 R 001 1 --> 001 1 R ; move R to Rend 002 0 --> 002 0 R 002 1 --> 003 1 R 003 0 --> 002 0 R 003 1 --> 004 1 L ; move L to buffer, unmark fsm entries 004 0 --> 005 0 L 004 1 --> 007 1 L 005 0 --> 006 0 L 005 1 --> 007 1 L 006 0 --> 006 0 L 006 1 --> 008 1 R 007 0 --> 004 0 L 007 1 --> jmp 1 L > find_nth_fsm_entry 008 0 --> 004 1 L 008 1 --> nop ;---------------------------------------------------------------------------- find_nth_fsm_entry: ; move L across buffer 000 0 --> 001 0 L 000 1 --> 000 1 L ; is n = 0? 001 0 --> jmp 1 L > decode_fsm_entry ; n = 0 001 1 --> 002 1 L ; n > 0 ; move L across n, decrement n 002 0 --> 009 0 R 002 1 --> 002 1 L ; move R across n 003 0 --> 004 0 R 003 1 --> 003 1 R ; more R across buffer 004 0 --> 005 0 R 004 1 --> 004 1 R ; move R to 011 (fsm entry) 005 0 --> 005 0 R 005 1 --> 006 1 R 006 0 --> 005 0 R 006 1 --> 007 0 L ; mark fsm entry ; move L to buffer 007 0 --> 007 0 L 007 1 --> 008 1 L 008 0 --> 007 0 L 008 1 --> 000 1 L 009 0 --> nop 009 1 --> 003 0 R ; (should reorder this) ;---------------------------------------------------------------------------- decode_fsm_entry: ; set n = 2 000 0 --> 001 1 R 000 1 --> nop ; move R across n 001 0 --> 002 0 R 001 1 --> 001 1 R ; move R across buffer 002 0 --> 003 0 R 002 1 --> 002 1 R ; move R to 011 (fsm entry in effect) 003 0 --> 003 0 R 003 1 --> 004 1 R 004 0 --> 003 0 R 004 1 --> 005 1 R ; ...011[0]... ; terminate fsm entry 005 0 --> 006 1 L ; ...01[1]1... 005 1 --> nop ; move L three squares 006 0 --> 007 0 L ; ...[x]0111... 006 1 --> 006 1 L ; two possibilities: to the left of the fsm entry in effect could be ; either another entry or Lend. 007 0 --> 008 0 L ; ...[x]00111... 007 1 --> 009 1 L ; ...[x]10111... 008 0 --> jmp 0 R > action_halt+1 ; ...0[0]0111... (hit another entry) 008 1 --> 010 1 L ; ...[x]100111... (crossed bit one) 009 0 --> 011 0 L ; ...[x]010111... (crossed bit zero) 009 1 --> jmp 1 R > action_halt ; ...1[1]0111... (hit Lend) ; start to the left of a bit, move L to Lend or next entry ; start with ...[x]10... 010 0 --> 011 0 L ; ...[x]10... 010 1 --> 013 1 R ; ...1[1]0... (hit Lend) ; start with ...[x]010... 011 0 --> 012 0 L ; ...[x]0010... 011 1 --> 010 1 L ; ...[x]1010... (crossed bit zero) ; start with ...[x]0010... 012 0 --> 014 0 R ; ...0[0]010... (hit another entry) 012 1 --> 010 1 L ; ...[x]10010... (crossed bit one) 013 0 --> nop 013 1 --> 014 1 R 014 0 --> 014 0 R 014 1 --> jmp 1 R > decode_state_field ;---------------------------------------------------------------------------- decode_state_field: ; move R to 1 000 0 --> 000 0 R 000 1 --> 001 1 R ; ...1[x]... ; have we finished decoding the state? 001 0 --> 002 1 R ; no, mark bit: ...11[x]... 001 1 --> jmp 1 R > decode_action_field ; yes, ...11[1]... ; is the bit zero or one? 002 0 --> 003 0 L ; ...1[1]0... (bit is one) 002 1 --> 004 1 L ; ...1[1]1... (bit it zero) 003 0 --> nop 003 1 --> jmp 1 L > fsm_state_bit_one ; ...[1]10... 004 0 --> nop 004 1 --> jmp 1 L > fsm_state_bit_zero ; ...[1]11... ;---------------------------------------------------------------------------- fsm_state_bit_zero: ; move L to buffer 000 0 --> 000 0 L 000 1 --> 001 1 L 001 0 --> 000 0 L 001 1 --> 002 1 L ; move L across buffer 002 0 --> 003 0 L 002 1 --> 002 1 L ; move L across n 003 0 --> jmp 0 R > double_n 003 1 --> 003 1 L ;---------------------------------------------------------------------------- fsm_state_bit_one: ; move L to buffer 000 0 --> 000 0 L 000 1 --> 001 1 L 001 0 --> 000 0 L 001 1 --> 002 1 L ; move L across buffer 002 0 --> 003 0 L 002 1 --> 002 1 L ; move L across n, set n = n + 1 003 0 --> 004 1 R 003 1 --> 003 1 L 004 0 --> nop 004 1 --> jmp 1 L > double_n ;---------------------------------------------------------------------------- double_n: ; double n 000 0 --> 003 0 R 000 1 --> 001 0 L 001 0 --> 002 1 R 001 1 --> 001 1 L 002 0 --> 000 1 R 002 1 --> 002 1 R ; move R across buffer 003 0 --> 004 0 R 003 1 --> 003 1 R ; move R to 011, unmark bit 004 0 --> 004 0 R 004 1 --> 005 1 R 005 0 --> 004 0 R 005 1 --> jmp 0 R > decode_state_field ;---------------------------------------------------------------------------- decode_action_field: ; start with ...11[1]0... 000 0 --> 001 0 R ; ...1100[x]... 000 1 --> 000 0 R ; ...110[0]... (un-terminate fsm entry) 001 0 --> 002 0 R ; ...11000[x]... 001 1 --> jmp 1 L > action_0R ; ...110[0]1... => action 0R 002 0 --> 003 0 R ; ...110000[x]... 002 1 --> jmp 1 L > action_1R ; ...1100[0]1... => action 1R 003 0 --> jmp 0 R > action_1L ; ...1100000[x]... => action 1L 003 1 --> jmp 1 R > action_0L ; ...1100001[x]... => action 0L ;---------------------------------------------------------------------------- action_0R: ; move L to buffer, move L across buffer 000 0 --> 000 0 L 000 1 --> 001 1 L 001 0 --> 000 0 L 001 1 --> 002 1 L 002 0 --> 000 0 L 002 1 --> 003 1 L 003 0 --> 004 0 L 003 1 --> nop ; move L across n 004 0 --> 005 0 L 004 1 --> 004 1 L ; move L to Lend 005 0 --> 005 0 L 005 1 --> jmp 0 R > action_0R_or_1R ; set old head = 0 ;---------------------------------------------------------------------------- action_1R: ; move L to buffer, move L across buffer 000 0 --> 000 0 L 000 1 --> 001 1 L 001 0 --> 000 0 L 001 1 --> 002 1 L 002 0 --> 000 0 L 002 1 --> 003 1 L 003 0 --> 004 0 L 003 1 --> nop ; move L across n 004 0 --> 005 0 L 004 1 --> 004 1 L ; move L to Lend 005 0 --> 005 0 L 005 1 --> jmp 1 R > action_0R_or_1R ; set old head = 1 ;---------------------------------------------------------------------------- action_0R_or_1R: ; shift UTM R one square 000 0 --> 001 1 R ; make Rend 000 1 --> nop ; move R to n (shifting R one square) 001 0 --> 001 0 R 001 1 --> 002 0 R ; move R across n (shifting R one square) 002 0 --> 009 1 R 002 1 --> 002 1 R ; move R across buffer (shifting R one square) 003 0 --> 004 1 R 003 1 --> 003 1 R ; move R to Rend (shifting R one square) 004 0 --> 004 0 R 004 1 --> 005 0 R 005 0 --> 004 1 R 005 1 --> 006 1 R 006 0 --> 004 1 R 006 1 --> 007 1 R ; move one square R, create new Rend 007 0 --> 008 1 R 007 1 --> 008 1 R ; move one square to R, test state of new head 008 0 --> jmp 0 L > action_0R_or_1R_head_0 008 1 --> jmp 1 L > action_0R_or_1R_head_1 009 0 --> nop 009 1 --> 003 0 R ;---------------------------------------------------------------------------- action_0R_or_1R_head_0: ; move L across Rend 000 0 --> 001 0 L 000 1 --> 000 1 L ; more L to buffer 001 0 --> 001 0 L 001 1 --> 002 1 L 002 0 --> 001 0 L 002 1 --> 003 1 L 003 0 --> 001 0 L 003 1 --> 004 1 L ; move L to n 004 0 --> 005 0 L 004 1 --> nop ; move L across n, set n = n-2 005 0 --> 006 0 R 005 1 --> 005 1 L 006 0 --> nop 006 1 --> 007 0 R 007 0 --> nop 007 1 --> jmp 0 R > main_loop ;---------------------------------------------------------------------------- action_0R_or_1R_head_1: ; move L across Rend 000 0 --> 001 0 L 000 1 --> 000 1 L ; move L to buffer 001 0 --> 001 0 L 001 1 --> 002 1 L 002 0 --> 001 0 L 002 1 --> 003 1 L 003 0 --> 001 0 L 003 1 --> 004 1 L ; move L to n 004 0 --> 005 0 L 004 1 --> nop ; move L across n, set n = n-1 005 0 --> 006 0 R 005 1 --> 005 1 L 006 0 --> nop 006 1 --> jmp 0 R > main_loop ;---------------------------------------------------------------------------- action_0L: ; move R to Rend 000 0 --> 000 0 R 000 1 --> 001 1 R 001 0 --> 000 0 R 001 1 --> 002 1 R 002 0 --> 000 0 R 002 1 --> 003 1 R ; set old head = 0 003 0 --> jmp 0 L > action_0L_or_1L 003 1 --> jmp 0 L > action_0L_or_1L ;---------------------------------------------------------------------------- action_1L: ; move R to Rend 000 0 --> 000 0 R 000 1 --> 001 1 R 001 0 --> 000 0 R 001 1 --> 002 1 R 002 0 --> 000 0 R 002 1 --> 003 1 R ; set old head = 1 003 0 --> jmp 1 L > action_0L_or_1L 003 1 --> jmp 1 L > action_0L_or_1L ;---------------------------------------------------------------------------- action_0L_or_1L: ; shift UTM L one bit ; move L across Rend (shifting L one bit) 000 0 --> 001 1 L 000 1 --> 000 1 L ; move L to buffer (shifting L one bit) 001 0 --> 001 0 L 001 1 --> 002 0 L 002 0 --> 001 1 L 002 1 --> 003 1 L 003 0 --> 001 1 L 003 1 --> 004 1 L ; move L to n (shifting L one bit) 004 0 --> 008 1 L 004 1 --> nop ; move L across n (shifting L one bit) 005 0 --> 006 1 L 005 1 --> 005 1 L ; move L to Lend (shifting L one bit) 006 0 --> 006 0 L 006 1 --> 007 0 L ; test state of new head, create new Lend 007 0 --> jmp 1 R > action_0L_or_L1_head_0 007 1 --> jmp 1 R > action_0L_or_L1_head_1 008 0 --> nop 008 1 --> 005 0 L ;---------------------------------------------------------------------------- action_0L_or_L1_head_0: ; move R to n, set n = n-2 000 0 --> 000 0 R 000 1 --> 001 0 R 001 0 --> nop 001 1 --> jmp 0 R > main_loop ;---------------------------------------------------------------------------- action_0L_or_L1_head_1: ; move R to n, set n = n-1 000 0 --> 000 0 R 000 1 --> jmp 0 R > main_loop ;---------------------------------------------------------------------------- action_halt: ; move R until 0 000 0 --> 002 0 R 000 1 --> 000 1 R ; move R until 1 001 0 --> 001 0 R 001 1 --> 002 0 R ; move R until 0 002 0 --> 003 0 R 002 1 --> 002 0 R ; determine action 003 0 --> 004 0 R 003 1 --> jmp 0 L > action_0R_halt 004 0 --> 005 0 R 004 1 --> jmp 0 L > action_1R_halt 005 0 --> jmp 0 L > action_0L_or_1L_halt 005 1 --> jmp 0 L > action_0L_or_1L_halt ;---------------------------------------------------------------------------- action_0R_halt: ; move L to buffer 000 0 --> 000 0 L 000 1 --> 001 0 L 001 0 --> 000 0 L 001 1 --> 002 0 L ; move L across buffer 002 0 --> 003 0 L 002 1 --> 002 0 L ; move L across n 003 0 --> 004 0 L 003 1 --> 003 0 L ; move L to Lend 004 0 --> 004 0 L 004 1 --> hlt 0 R ;---------------------------------------------------------------------------- action_1R_halt: ; move L to buffer 000 0 --> 000 0 L 000 1 --> 001 0 L 001 0 --> 000 0 L 001 1 --> 002 0 L ; move L across buffer 002 0 --> 003 0 L 002 1 --> 002 0 L ; move L across n 003 0 --> 004 0 L 003 1 --> 003 0 L ; move L to Lend 004 0 --> 004 0 L 004 1 --> hlt 1 R ;---------------------------------------------------------------------------- action_0L_or_1L_halt: ; move L to buffer 000 0 --> 000 0 L 000 1 --> 001 0 L 001 0 --> 000 0 L 001 1 --> 002 0 L ; move L across buffer 002 0 --> 003 0 L 002 1 --> 002 0 L ; move L across n 003 0 --> 004 0 L 003 1 --> 003 0 L ; move L to Lend 004 0 --> 004 0 L 004 1 --> hlt 0 L