Rosetta Code

Universal Turing machine: Difference between revisions

Page Discussion

Universal Turing machine (view source)

Revision as of 10:30, 15 February 2024

1,152 bytes removed ,  4 months ago
m
→‎{{header|Wren}}: Minor tidy
m (→‎{{header|Wren}}: Minor tidy)
 
(13 intermediate revisions by 2 users not shown)
Line 761:
 
=={{header|APL}}==
===⍺===
{{works with|Dyalog APL}}
<syntaxhighlight lang="apl">:Namespace Turing
Line 843 ⟶ 844:
2_ThreeStateBeaver: 111111
3_FiveStateBeaver: 10100100100100100100100100100100... (total length: 12289)</pre>
 
===⍵===
 
{{works with|Dyalog APL}}
 
<syntaxhighlight lang="lisp">
∆I ←'QA.1' '1' 'R' 'QA'
∆I,←'QA.B' '1' 'N' 'QB'
∆INCREMENTER←∆I
 
∆B ←'QA.0' '1' 'R' 'QB'
∆B,←'QA.1' '1' 'L' 'QC'
∆B,←'QB.0' '1' 'L' 'QA'
∆B,←'QB.1' '1' 'R' 'QB'
∆B,←'QC.0' '1' 'L' 'QB'
∆B,←'QC.1' '1' 'N' 'QD'
∆BEAVER←∆B
 
∇ R←RUN(F Q H T B);I;J
I←1 ⋄ T←,T
L:→(Q≡H)/E
J←⍸(Q,'.',T[I])∘≡¨F
T[I]←F[J+1]
I←I+2-'RNL'⍳F[J+2]
Q←⊃F[J+3]
T←((I<1)⍴B),T,(I>⍴T)⍴B
I←I+I=0
→L
E:R←T I
∇
</syntaxhighlight>
 
{{out}}
<pre>
RUN ∆INCREMENTER 'QA' 'QB' '111' 'B'
1111 4
RUN ∆BEAVER 'QA' 'QD' '0' '0'
111111 4
</pre>
 
=={{header|AutoHotkey}}==
Line 2,372 ⟶ 2,412:
5-state busy beaver (first 20 cells)
10100100100100100100...</pre>
===Control language===
Tmcl is a tiny Turing machine control language.
 
====Instruction set====
 
Tmcl uses postfix notation.
 
<pre>'=' : if scanned symbol = op do
'%' : print op
'<' : move left
'>' : move right
'@' : state <- op
<symbol> : op <- symbol</pre>
 
====Program====
 
Tape is split into two stacks.
 
<pre>T = reverse (left) . right where right is the scanned symbol.
0</pre>
 
<syntaxhighlight lang="lisp">;; 22.11.23 (Mise en forme du code)
 
(defun run (program input state halt blank)
(let ((left nil)
(right input)
(operand nil)
(match nil))
(loop until (equal state halt)
do (setf routine (rest (assoc state program)))
(setf match t)
(dolist (token routine)
(case token
(= (setf match (equal (first right) operand)))
(% (when match (rplaca right operand)))
(< (when match (push (pop left) right)))
(> (when match (push (pop right) left)))
(@ (when match (setf state operand) (return)))
(t (setf operand token)))
(unless (first right)
(setf right (cons blank (rest right))))))
(format t "Q = <~a, ~{~a~}.~{~a~}>~%" state (reverse left) right)))</syntaxhighlight>
 
====Code====
 
code is stored in association lists.
 
<syntaxhighlight lang="lisp">(defconstant +incrementer+ '((q0 . (1 = > q0 @ b = 1 % qf @))))
 
(defconstant +three-states-buzy-beaver+ '((a . (0 = 1 % > b @ 1 = < c @))
(b . (0 = 1 % < a @ 1 = > b @))
(c . (0 = 1 % < b @ 1 = halt @))))</syntaxhighlight>
 
====Execution====
 
{{out}}
<pre>(run +incrementer+ '(1 1 1) 'q0 '(qf) 'b)
Q = <QF 111.1>
(run +three-states-buzy-beaver+ '(0) 'a '(halt) '0)
Q = <HALT 111.111></pre>
 
''cyril nocton (cyril.nocton@gmail.com) w/ google translate''
 
=={{header|Cowgol}}==
<syntaxhighlight lang="cowgol">include "cowgol.coh";
Line 4,534 ⟶ 4,511:
=={{header|Fōrmulæ}}==
 
{{FormulaeEntry|page=https://formulae.org/?script=examples/Universal_Turing_machine}}
Fōrmulæ programs are not textual, visualization/edition of programs is done showing/manipulating structures but not text. Moreover, there can be multiple visual representations of the same program. Even though it is possible to have textual representation &mdash;i.e. XML, JSON&mdash; they are intended for storage and transfer purposes more than visualization and edition.
 
'''Solution'''
 
[[File:Fōrmulæ - Universal Turing machine 01.png]]
 
'''Test case 1. Simple incrementer'''
 
[[File:Fōrmulæ - Universal Turing machine 02.png]]
 
[[File:Fōrmulæ - Universal Turing machine 03.png]]
 
'''Test case 2. One-state busy beaver game'''
 
[[File:Fōrmulæ - Universal Turing machine 04.png]]
 
[[File:Fōrmulæ - Universal Turing machine 05.png]]
 
'''Test case 3. Two-state busy beaver game'''
 
[[File:Fōrmulæ - Universal Turing machine 06.png]]
 
[[File:Fōrmulæ - Universal Turing machine 07.png]]
 
'''Test case 4. Three-state busy beaver game'''
 
[[File:Fōrmulæ - Universal Turing machine 08.png]]
 
[[File:Fōrmulæ - Universal Turing machine 09.png]]
 
'''Test case 5. Four-state busy beaver game'''
 
[[File:Fōrmulæ - Universal Turing machine 10.png]]
 
[[File:Fōrmulæ - Universal Turing machine 11.png]]
 
'''Test case 6. (Probable) Five-state busy beaver game'''
 
In this case, the length of the tape is returned, and not the tape itself.
 
This machine will run for more than 47 millions steps.
 
[[File:Fōrmulæ - Universal Turing machine 12.png]]
Programs in Fōrmulæ are created/edited online in its [https://formulae.org website], However they run on execution servers. By default remote servers are used, but they are limited in memory and processing power, since they are intended for demonstration and casual use. A local server can be downloaded and installed, it has no limitations (it runs in your own computer). Because of that, example programs can be fully visualized and edited, but some of them will not run if they require a moderate or heavy computation/memory resources, and no local server is being used.
 
[[File:Fōrmulæ - Universal Turing machine 13.png]]
In '''[https://formulae.org/?example=Universal_Turing_machine this]''' page you can see the program(s) related to this task and their results.
 
=={{header|Go}}==
Line 12,302 ⟶ 12,319:
{{libheader|Wren-dynamic}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="ecmascriptwren">import "./dynamic" for Enum, Tuple, Struct
import "./fmt" for Fmt
 
var Dir = Enum.create("Dir", ["LEFT", "RIGHT", "STAY"])
PureFox
9,486

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/333832...351924"