How to resolve the algorithm Universal Turing machine step by step in the Amazing Hopper programming language

Published on 12 May 2024 09:40 PM
#Amazing hopper

How to resolve the algorithm Universal Turing machine step by step in the Amazing Hopper 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 Amazing Hopper programming language

Source code in the amazing programming language

#include 
#proto UniversalTuringMachine(_X_)
 
main:
  .ctrlc
 
   stbegin=0,stEnd=0,state=0,ptr=0
   tape=0,states=0,rules=0,long=0,tapeSize=0
   file="turing/prg03.tm"
 
  // load program, rules & states:
   jsub(load Archive)
 
 // RUN Universal Turing Machine program:
  i=1
  __TURING_RUN__:
      _Universal Turing Machine ([i,1:end]get(rules))
      ++i,{long,i}gt? do{  i=1  }
      jt(__TURING_RUN__)
  println
exit(0)
 
.locals
 
printTape:
#hl{
  print(tape[1:(ptr-1)],"\R",tape[ptr],"\OFF",tape[(ptr+1):end],"\n")
  //sleep(0.1)
  }
  up(1)
  clear mark
back
 
Universal Turing Machine(rules)
  cont=1
  clear mark
 
  #hl{
     if( rules[1] == state )
        if( tape[ptr] == rules[2] )
           tape[ptr] = rules[3]
           ptr += rules[4]
           if(ptr==0)
  }
              ++tapeSize
              {0,1,tape}, array(INSERT), ++ptr
  #hl{
           else if(ptr>tapeSize)
  }
              ++tapeSize
              {tapeSize,tape},array(RESIZE),
              [tapeSize]{0},put(tape),clear mark
  #hl{
           endif
           state = rules[5]
           if(state == stEnd)
              cont=0
           endif
  }
           jsub(print Tape)
  #hl{
        endif
     endif
  }, {cont}
back
 
load Archive:
  {","}tok sep
  {file} stats file
  [1,1:end],{file},!(5),load, mov(tape)
  [2,1:3],         !(5),load, mov(states)
  [3:end,1:5],          load, mov(rules)
  clear mark
  [1:end,4]get(rules),colMoving=0,   mov(colMoving)
  {"1","RIGHT",colMoving} transform, mov(colMoving)
  {"-1","LEFT",colMoving} transform, mov(colMoving)
  {"0","STAY",colMoving}  transform, xtonum, put(rules)
  clear mark
  {0}reshape(tape)
  size(tape),lengthTape=0,mov(lengthTape),[2]get(lengthTape),mov(tapeSize)
  #hl{
     stbegin=states[1,1]
     stEnd=states[1,2]
     ptr=states[1,3]
     state=stbegin
  }
  data rules=0, size(rules), mov(datarules), [2]get(data rules), mov(long)
  {""}tok sep
back

You may also check:How to resolve the algorithm Longest increasing subsequence step by step in the Java programming language
You may also check:How to resolve the algorithm GUI component interaction step by step in the Liberty BASIC programming language
You may also check:How to resolve the algorithm Create an HTML table step by step in the VBA programming language
You may also check:How to resolve the algorithm Hailstone sequence step by step in the Batch File programming language
You may also check:How to resolve the algorithm Address of a variable step by step in the Scala programming language