Universal Turing machine: Difference between revisions

Content added Content deleted
Line 2,372: Line 2,372:
5-state busy beaver (first 20 cells)
5-state busy beaver (first 20 cells)
10100100100100100100...</pre>
10100100100100100100...</pre>
===Control language===
===Acl===
⚫
Tmcl is a tiny Turing machine control language.


⚫
Acl is a tiny a-machine control language. Instructions are
====Instruction set====


⚫
<pre>'=' : if scanned symbol = arg do
Tmcl uses postfix notation.
⚫
'%' : print arg

⚫
<pre>'=' : if scanned symbol = op do
⚫
'%' : print op
'<' : move left
'<' : move left
'>' : move right
'>' : move right
'@' : state <- op
'@' : state <- arg
<symbol> : op <- symbol</pre>
<symbol> : arg <- symbol</pre>


====Program====
====Program====
Line 2,390: Line 2,387:
Tape is split into two stacks.
Tape is split into two stacks.


<pre>T = reverse (left) . right where right is the scanned symbol.
<pre>T = reverse (l) . r where r is the scanned symbol.
0</pre>
0</pre>


<syntaxhighlight lang="lisp">;; 22.11.23 (Mise en forme du code)
<syntaxhighlight lang="lisp">;; 22.12.23


(defun run (program input state halt blank)
(defun acl (table input state halt blank)
(let ((left nil)
(let ((l nil)
(right input)
(r input)
(operand nil)
(arg nil)
(match nil))
(exe nil))
(loop until (equal state halt)
(loop :until (equal state halt)
do (setf routine (rest (assoc state program)))
:do (setf code (cdr (assoc state table))
(setf match t)
exe t)
(dolist (token routine)
(dolist (c code)
(case token
(case c
(= (setf match (equal (first right) operand)))
(= (setf exe (equal (car r) arg)))
(% (when match (rplaca right operand)))
(% (when exe (rplaca r arg)))
(< (when match (push (pop left) right)))
(< (when exe (push (pop l) r)))
(> (when match (push (pop right) left)))
(> (when exe (push (pop r) l)))
(@ (when match (setf state operand) (return)))
(@ (when exe (setf state arg) (return)))
(t (setf operand token)))
(t (setf arg c)))
(unless (first right)
(unless (car r)
(setf right (cons blank (rest right))))))
(setf r (cons blank (cdr r))))))
(format t "Q = <~a, ~{~a~}.~{~a~}>~%" state (reverse left) right)))</syntaxhighlight>
(format t "Q = <~a, ~{~a~}.~{~a~}>~%" state (reverse l) r)))</syntaxhighlight>


====Code====
====Tables====


code is stored in association lists.
Tables are stored in association lists.


<syntaxhighlight lang="lisp">(defconstant +incrementer+ '((q0 . (1 = > q0 @ b = 1 % qf @))))
<syntaxhighlight lang="lisp">(defconstant +incrementer+ '((q0 . (1 = > q0 @ b = 1 % qf @))))
Line 2,426: Line 2,423:


====Execution====
====Execution====

⚫
<pre>(acl +incrementer+ '(1 1 1) 'q0 'qf 'b)
⚫
(acl +three-states-buzy-beaver+ '(0) 'a 'halt '0)</pre>


{{out}}
{{out}}
<pre>
⚫
<pre>(run +incrementer+ '(1 1 1) 'q0 '(qf) 'b)
Q = <QF, 111.1>
Q = <QF, 111.1>
⚫
(run +three-states-buzy-beaver+ '(0) 'a '(halt) '0)
Q = <HALT, 111.111></pre>
Q = <HALT, 111.111></pre>


Retrieved from "https://rosettacode.org/wiki/Universal_Turing_machine"