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

Published on 12 May 2024 09:40 PM
#Prolog

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

Source code in the prolog programming language

turing(Config, Rules, TapeIn, TapeOut) :-
    call(Config, IS, _, _, _, _),
    perform(Config, Rules, IS, {[], TapeIn}, {Ls, Rs}),
    reverse(Ls, Ls1),
    append(Ls1, Rs, TapeOut).

perform(Config, Rules, State, TapeIn, TapeOut) :-
    call(Config, _, FS, RS, B, Symbols),
    ( memberchk(State, FS) ->
        TapeOut = TapeIn
    ; memberchk(State, RS) ->
        {LeftIn, RightIn} = TapeIn,
        symbol(RightIn, Symbol, RightRem, B),
        memberchk(Symbol, Symbols),
        once(call(Rules, State, Symbol, NewSymbol, Action, NewState)),
        memberchk(NewSymbol, Symbols),
        action(Action, {LeftIn, [NewSymbol|RightRem]}, {LeftOut, RightOut}, B),
        perform(Config, Rules, NewState, {LeftOut, RightOut}, TapeOut) ).

symbol([],       B,   [], B).
symbol([Sym|Rs], Sym, Rs, _).

action(left,  {Lin, Rin},  {Lout, Rout}, B) :- left(Lin, Rin, Lout, Rout, B).
action(stay,  Tape,        Tape,         _).
action(right, {Lin, Rin},  {Lout, Rout}, B) :- right(Lin, Rin, Lout, Rout, B).

left([],     Rs, [], [B|Rs], B).
left([L|Ls], Rs, Ls, [L|Rs], _).

right(L, [],     [B|L], [], B).
right(L, [S|Rs], [S|L], Rs, _).


incrementer_config(IS, FS, RS, B, S) :-
    IS = q0,      % initial state
    FS = [qf],    % halting states
    RS = [IS],    % running states
    B  = 0,       % blank symbol
    S  = [B, 1].  % valid symbols
incrementer(q0, 1, 1, right, q0).
incrementer(q0, b, 1, stay,  qf).

turing(incrementer_config, incrementer, [1, 1, 1], TapeOut).


busy_beaver_config(IS, FS, RS, B, S) :-
    IS = 'A',               % initial state
    FS = ['HALT'],          % halting states
    RS = [IS, 'B', 'C'],    % running states
    B  = 0,                 % blank symbol
    S  = [B, 1].            % valid symbols
busy_beaver('A', 0, 1, right, 'B').
busy_beaver('A', 1, 1, left,  'C').
busy_beaver('B', 0, 1, left,  'A').
busy_beaver('B', 1, 1, right, 'B').
busy_beaver('C', 0, 1, left,  'B').
busy_beaver('C', 1, 1, stay,  'HALT').

turing(busy_beaver_config, busy_beaver, [], TapeOut).

You may also check:How to resolve the algorithm Towers of Hanoi step by step in the PL/M programming language
You may also check:How to resolve the algorithm Set, the card game step by step in the Factor programming language
You may also check:How to resolve the algorithm Shell one-liner step by step in the S-lang programming language
You may also check:How to resolve the algorithm Sierpinski triangle/Graphical step by step in the R programming language
You may also check:How to resolve the algorithm Longest common substring step by step in the Bracmat programming language