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

Published on 12 May 2024 09:40 PM
#Javascript

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

This code implements a rudimentary Turing machine in JavaScript. The function tm accepts seven arguments:

  • d: a string describing the Turing machine
  • s: the initial state of the machine
  • e: the halting state of the machine
  • i: the initial position of the tape head
  • b: the blank symbol
  • t: the initial contents of the tape
  • ...r: a list of rules for the machine

Each rule is a string of the form s.r: w,m,n, where:

  • s is the current state of the machine
  • r is the symbol that is currently being read from the tape
  • w is the symbol that should be written to the tape
  • m is the direction that the tape head should move (L=left, R=right)
  • n is the next state of the machine

The function works by repeatedly applying the rules to the current state of the machine and tape. If the machine is in the halting state, the function stops. Otherwise, the function continues to apply the rules until the machine reaches the halting state. In the provided examples, the function implements:

  • A unary incrementer
  • A unary adder
  • A three-state busy beaver

Source code in the javascript programming language

function tm(d,s,e,i,b,t,... r) {
	document.write(d, '<br>')
	if (i<0||i>=t.length) return
	var re=new RegExp(b,'g')
	write('*',s,i,t=t.split(''))
	var p={}; r.forEach(e=>((s,r,w,m,n)=>{p[s+'.'+r]={w,n,m:[0,1,-1][1+'RL'.indexOf(m)]}})(... e.split(/[ .:,]+/)))
	for (var n=1; s!=e; n+=1) {
		with (p[s+'.'+t[i]]) t[i]=w,s=n,i+=m
		if (i==-1) i=0,t.unshift(b)
		else if (i==t.length) t[i]=b
		write(n,s,i,t)
	}
	document.write('<br>')
	function write(n, s, i, t) {
		t = t.join('')
		t = t.substring(0,i) + '<u>' + t.charAt(i) + '</u>' + t.substr(i+1)
		document.write(('  '+n).slice(-3).replace(/ /g,'&nbsp;'), ': ', s, ' [', t.replace(re,'&nbsp;'), ']', '<br>')
	}
}

tm( 'Unary incrementer',
//	 s    e   i   b    t
	'a', 'h', 0, 'B', '111',
//	 s.r: w, m, n
	'a.1: 1, L, a',
	'a.B: 1, S, h'
)

tm( 'Unary adder',
	1, 0, 0, '0', '1110111',
	'1.1: 0, R, 2', // write 0 rigth goto 2
	'2.1: 1, R, 2', // while (1) rigth
	'2.0: 1, S, 0'  // write 1 stay halt
)

tm( 'Three-state busy beaver',
	1, 0, 0, '0', '0',
	'1.0: 1, R, 2',
	'1.1: 1, R, 0',
	'2.0: 0, R, 3',
	'2.1: 1, R, 2',
	'3.0: 1, L, 3',
	'3.1: 1, L, 1'
)

You may also check:How to resolve the algorithm Modular inverse step by step in the JavaScript programming language
You may also check:How to resolve the algorithm Pangram checker step by step in the JavaScript programming language
You may also check:How to resolve the algorithm Egyptian division step by step in the JavaScript programming language
You may also check:How to resolve the algorithm Cistercian numerals step by step in the JavaScript programming language
You may also check:How to resolve the algorithm 24 game step by step in the JavaScript programming language