How to resolve the algorithm Universal Turing machine step by step in the PicoLisp programming language
How to resolve the algorithm Universal Turing machine step by step in the PicoLisp programming language
Table of Contents
Problem Statement
One of the foundational mathematical constructs behind computer science is the universal Turing Machine.
(Alan Turing introduced the idea of such a machine in 1936–1937.) Indeed one way to definitively prove that a language is turing-complete is to implement a universal Turing machine in it.
Simulate such a machine capable
of taking the definition of any other Turing machine and executing it.
Of course, you will not have an infinite tape,
but you should emulate this as much as is possible.
The three permissible actions on the tape are "left", "right" and "stay".
To test your universal Turing machine (and prove your programming language
is Turing complete!), you should execute the following two Turing machines
based on the following definitions.
Simple incrementer
The input for this machine should be a tape of 1 1 1
Three-state busy beaver
The input for this machine should be an empty tape.
Bonus: 5-state, 2-symbol probable Busy Beaver machine from Wikipedia
The input for this machine should be an empty tape. This machine runs for more than 47 millions steps.
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Universal Turing machine step by step in the PicoLisp programming language
Source code in the picolisp programming language
# Finite state machine
(de turing (Tape Init Halt Blank Rules Verbose)
(let
(Head 1
State Init
Rule NIL
S 'start
C (length Tape))
(catch NIL
(loop
(state 'S
(start 'print
(when (=0 C)
(setq Tape (insert Head Tape Blank))
(inc 'C) ) )
(print 'lookup
(when Verbose
(for (N . I) Tape
(if (= N Head)
(print (list I))
(prin I) ) )
(prinl) )
(when (= State Halt) (throw NIL) ) )
(lookup 'do
(setq Rule
(find
'((X)
(and
(= (car X) State)
(= (cadr X) (car (nth Tape Head))) ) )
Rules ) ) )
(do 'step
(setq Tape (place Head Tape (caddr Rule))) )
(step 'print
(cond
((= (cadddr Rule) 'R) (inc 'Head))
((= (cadddr Rule) 'L) (dec 'Head)) )
(cond
((< Head 1)
(setq Tape (insert Head Tape Blank))
(inc 'C)
(one Head) )
((> Head C)
(setq Tape (insert Head Tape Blank))
(inc 'C) ) )
(setq State (last Rule)) ) ) ) ) )
Tape )
(println "Simple incrementer")
(turing '(1 1 1) 'A 'H 'B '((A 1 1 R A) (A B 1 S H)) T)
(println "Three-state busy beaver")
(turing '() 'A 'H 0
'((A 0 1 R B)
(A 1 1 L C)
(B 0 1 L A)
(B 1 1 R B)
(C 0 1 L B)
(C 1 1 S H)) T )
(println "Five-state busy beaver")
(let Tape (turing '() 'A 'H 0
'((A 0 1 R B)
(A 1 1 L C)
(B 0 1 R C)
(B 1 1 R B)
(C 0 1 R D)
(C 1 0 L E)
(D 0 1 L A)
(D 1 1 L D)
(E 0 1 S H)
(E 1 0 L A)) NIL)
(println '0s: (cnt '((X) (= 0 X)) Tape))
(println '1s: (cnt '((X) (= 1 X)) Tape)) )
(bye)
You may also check:How to resolve the algorithm Collections step by step in the Lua programming language
You may also check:How to resolve the algorithm RSA code step by step in the Python programming language
You may also check:How to resolve the algorithm Integer sequence step by step in the AutoHotkey programming language
You may also check:How to resolve the algorithm Numbers which are the cube roots of the product of their proper divisors step by step in the J programming language
You may also check:How to resolve the algorithm 15 puzzle game step by step in the REXX programming language