How to resolve the algorithm Universal Turing machine step by step in the REXX programming language
Published on 12 May 2024 09:40 PM
How to resolve the algorithm Universal Turing machine step by step in the REXX 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 REXX programming language
Source code in the rexx programming language
/*REXX program executes a Turing machine based on initial state, tape, and rules. */
state = 'q0' /*the initial Turing machine state. */
term = 'qf' /*a state that is used for a halt. */
blank = 'B' /*this character is a "true" blank. */
call Turing_rule 'q0 1 1 right q0' /*define a rule for the Turing machine.*/
call Turing_rule 'q0 B 1 stay qf' /* " " " " " " " */
call Turing_init 1 1 1 /*initialize the tape to some string(s)*/
call TM /*go and invoke the Turning machine. */
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
TM: !=1; bot=1; top=1; @er= '***error***' /*start at the tape location 1. */
say /*might as well display a blank line. */
do cycle=1 until state==term /*process Turing machine instructions.*/
do k=1 for rules /* " " " rules. */
parse var rule.k rState rTape rWrite rMove rNext . /*pick pieces. */
if state\==rState | @.!\==rTape then iterate /*wrong rule ? */
@.!=rWrite /*right rule; write it ───► the tape. */
if rMove== 'left' then !=!-1 /*Are we moving left? Then subtract 1*/
if rMove=='right' then !=!+1 /* " " " right? " add 1*/
bot=min(bot, !); top=max(top, !) /*find the tape bottom and top. */
state=rNext; iterate cycle /*use this for the next state; and */
end /*k*/
say @er 'unknown state:' state; leave /*oops, we have an unknown state error.*/
end /*cycle*/
$= /*start with empty string (the tape). */
do t=bot to top; _=@.t
if _==blank then _=' ' /*do we need to translate a true blank?*/
$=$ || pad || _ /*construct char by char, maybe pad it.*/
end /*t*/ /* [↑] construct the tape's contents*/
L=length($) /*obtain length of " " " */
if L==0 then $= "[tape is blank.]" /*make an empty tape visible to user.*/
if L>1000 then $=left($, 1000) ... /*truncate tape to 1k bytes, append ···*/
say "tape's contents:" $ /*show the tape's contents (or 1st 1k).*/
say "tape's length: " L /* " " " length. */
say 'Turning machine used ' rules " rules in " cycle ' cycles.'
return
/*──────────────────────────────────────────────────────────────────────────────────────*/
Turing_init: @.=blank; parse arg x; do j=1 for words(x); @.j=word(x,j); end /*j*/
return
/*──────────────────────────────────────────────────────────────────────────────────────*/
Turing_rule: if symbol('RULES')=="LIT" then rules=0; rules=rules+1
pad=left('', length( word( arg(1),2 ) ) \==1 ) /*padding for rule*/
rule.rules=arg(1); say right('rule' rules, 20) "═══►" rule.rules
return
/*REXX program executes a Turing machine based on initial state, tape, and rules. */
state = 'a' /*the initial Turing machine state. */
term = 'halt' /*a state that is used for a halt. */
blank = 0 /*this character is a "true" blank. */
call Turing_rule 'a 0 1 right b' /*define a rule for the Turing machine.*/
call Turing_rule 'a 1 1 left c' /* " " " " " " " */
call Turing_rule 'b 0 1 left a' /* " " " " " " " */
call Turing_rule 'b 1 1 right b' /* " " " " " " " */
call Turing_rule 'c 0 1 left b' /* " " " " " " " */
call Turing_rule 'c 1 1 stay halt' /* " " " " " " " */
call Turing_init /*initialize the tape to some string(s)*/
call TM /*go and invoke the Turning machine. */
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
TM: ∙∙∙
/*REXX program executes a Turing machine based on initial state, tape, and rules. */
state = 'A' /*initialize the Turing machine state.*/
term = 'H' /*a state that is used for the halt. */
blank = 0 /*this character is a "true" blank. */
call Turing_rule 'A 0 1 right B' /*define a rule for the Turing machine.*/
call Turing_rule 'A 1 1 left C' /* " " " " " " " */
call Turing_rule 'B 0 1 right C' /* " " " " " " " */
call Turing_rule 'B 1 1 right B' /* " " " " " " " */
call Turing_rule 'C 0 1 right D' /* " " " " " " " */
call Turing_rule 'C 1 0 left E' /* " " " " " " " */
call Turing_rule 'D 0 1 left A' /* " " " " " " " */
call Turing_rule 'D 1 1 left D' /* " " " " " " " */
call Turing_rule 'E 0 1 stay H' /* " " " " " " " */
call Turing_rule 'E 1 0 left A' /* " " " " " " " */
call Turing_init /*initialize the tape to some string(s)*/
call TM /*go and invoke the Turning machine. */
exit /*stick a fork in it, we're done.*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
TM: ∙∙∙
/*REXX program executes a Turing machine based on initial state, tape, and rules. */
state = 'A' /*the initial Turing machine state. */
term = 'halt' /*a state that is used for the halt. */
blank = 0 /*this character is a "true" blank. */
call Turing_rule 'A 1 1 right A' /*define a rule for the Turing machine.*/
call Turing_rule 'A 2 3 right B' /* " " " " " " " */
call Turing_rule 'A 0 0 left E' /* " " " " " " " */
call Turing_rule 'B 1 1 right B' /* " " " " " " " */
call Turing_rule 'B 2 2 right B' /* " " " " " " " */
call Turing_rule 'B 0 0 left C' /* " " " " " " " */
call Turing_rule 'C 1 2 left D' /* " " " " " " " */
call Turing_rule 'C 2 2 left C' /* " " " " " " " */
call Turing_rule 'C 3 2 left E' /* " " " " " " " */
call Turing_rule 'D 1 1 left D' /* " " " " " " " */
call Turing_rule 'D 2 2 left D' /* " " " " " " " */
call Turing_rule 'D 3 1 right A' /* " " " " " " " */
call Turing_rule 'E 1 1 left E' /* " " " " " " " */
call Turing_rule 'E 0 0 right halt' /* " " " " " " " */
call Turing_init 1 2 2 1 2 2 1 2 1 2 1 2 1 2 /*initialize the tape to some string(s)*/
call TM /*go and invoke the Turning machine. */
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
TM: ∙∙∙
You may also check:How to resolve the algorithm Runge-Kutta method step by step in the Ring programming language
You may also check:How to resolve the algorithm Multisplit step by step in the XPL0 programming language
You may also check:How to resolve the algorithm Roman numerals/Decode step by step in the Clojure programming language
You may also check:How to resolve the algorithm Sorting algorithms/Cocktail sort step by step in the Elena programming language
You may also check:How to resolve the algorithm Text processing/2 step by step in the Wren programming language