# Takes a tape representing a natural number k (see Boolos, Burgess # and Jeffrey for definition) and returns a tape representing a pair # . (0,1, ,1,r) (0, , ,99,r) (1, , ,2,r) # Look for blank (1,1,1,1,r) (2, ,1,3,r) # Wrote my 1. (2,1,1,2,r) (3, , ,4,r) (3,1, ,5,r) (4, ,1,6,l) (5, ,1,7,r) (5,1,1,5,4) (6, , ,8,l) (6,1,1,6,l) (7, ,1,6,l) (8, , ,9,l) (8,1,1,8,l) (9, , ,0,r) (9,1,1,9,l) (9,1,1,1000,r) # Former halt state. (8,1,1,1000,r) # Former halt state. (7,1,1,1000,r) # Former halt state. (6,1,1,1000,r) # Former halt state. (5,1,1,1000,r) # Former halt state. (4,1,1,1000,r) # Former halt state. (2,1,1,1000,r) # Former halt state. (1,1,1,1000,r) # Former halt state. (99, , ,1000,r) # Former halt state. (99,1,1,1000,r) # Former halt state. # Skip this block of one's, goto next (100,1,1,100,r) (100, , ,101,r) (101, , ,101,r) (101,1,1,102,l) (102, , ,103,r) (1000, , ,100,l) #Goto start state, machine skip (1000,1,1,100,l) #Goto start state, machine skip