Universal Turing machine: Difference between revisions

{{trans|Python}}

 

V st = state

I tape.empty

‘E 0 0 right STOP’.split(‘ ’, group_delimiters' 1B)],

tape' &‘2 2 2 1 2 2 1 2 1 2 1 2 1 2’.split(‘ ’).map(Char)

 

{{out}}

The execution of the machine, i.e., the procedure Run, allows to define a number Max_Steps, after which the execution stops -- when, e.g., the specified machine runs infinitively. The procedure also allows to optionally output the configuration of the machine before every step.

 

 

generic

Right: List;

end record;

 

===The implementation of the universal machine===

 

 

function List_To_String(L: List; Map: Symbol_Map) return String is

end Run;

 

 

 

===The implementation of the simple incrementer===

 

 

procedure Simple_Incrementer is

Run(Tape, Rules, 20, null); -- don't print the configuration during running

Put_Tape(Tape, Stop); -- print the final configuration

 

{{out}}

===The implementation of the busy beaver===

 

 

procedure Busy_Beaver_3 is

Run(Tape, Rules, 20, Put_Tape'Access); -- print configuration before each step

Put_Tape(Tape, Stop); -- and print the final configuration

 

{{out}}

=={{header|Amazing Hopper}}==

Implementation of a Universal Turing Machine:

#include <hopper.h>

#proto UniversalTuringMachine(_X_)

{""}tok sep

back

ALternative pseudo-function UniversalTuringMachine (fast):

<pre>

 

=={{header|APL}}==

{{works with|Dyalog APL}}

⍝ Run Turing machine until it halts

∇r←RunTuring (rules init halts blank itape);state;rt;lt;next

:EndFor

∇

{{out}}

<pre>1_SimpleIncrementer: 1111

2_ThreeStateBeaver: 111111

3_FiveStateBeaver: 10100100100100100100100100100100... (total length: 12289)</pre>

 

=={{header|AutoHotkey}}==

SetBatchLines, -1

OnExit, Exit

If (A_Gui = 1)

PostMessage, 0xA1, 2

<b>Input:</b>

Set Section below to desired machine, then save as <scriptname>.ini in the same folder.

 

<b>Non-universality:</b> as written, the program will fail if you try to use it with a Turing machine that has more than 256 distinct states or a tape that is longer than 704 cells. (In reality, of course, the ZX81's RAM would have been exhausted some time before you reached such a Goliath.) Allowing more states would be pretty trivial, assuming you had the memory space; just use as many bytes as you need. As for supporting a longer tape, the easiest way to do it would be to comment out the <code>PRINT</code> statements (sacrificing the animation) and add a few lines to display one screenful at a time at the very end.

1010 LET P=1

1020 IF P>LEN T$ THEN LET T$=T$+B$

1150 GOTO 1020

1160 LET T$=B$+T$

 

====The incrementer====

Works with 1k of RAM.

20 LET S$=CHR$ (CODE "Q"+CODE "0")

30 LET H$=CHR$ (CODE "Q"+CODE "F")

50 LET R$(2)=S$+"B1S"+H$

60 LET B$="B"

{{out}}

<pre>1111</pre>

====The three-state beaver====

Requires at least 2k of RAM.

20 LET R$(1)="A01RB"

30 LET R$(2)="A11LC"

90 LET S$="A"

100 LET B$="0"

{{out}}

<pre>111111</pre>

 

=={{header|C}}==

#include <stdarg.h>

#include <stdlib.h>

run(t);

}

 

{{output}}

 

=={{header|C sharp}}==

using System.Collections.Generic;

using System.Diagnostics;

}

 

{{out}}

<pre style="height:30ex;overflow:scroll">

 

=={{header|C++}}==

#include <vector>

#include <string>

int main( int a, char* args[] ){ utm mm; mm.start(); return 0; }

//--------------------------------------------------------------------------------------------------

 

'''These are the files you'll need'''<br />

 

=={{header|Clojure}}==

(defn tape

"Creates a new tape with given blank character and tape contents"

(let [[out action new-state] (get rules [state (head tape)])]

(recur new-state (action tape out))))))))

 

=== Tests ===

 

(def simple-incrementer

(new-machine {:initial :q0

(is (= 4098 (get freq 1)))

(is (= 8191 (get freq 0)))))

 

=={{header|CLU}}==

tape = cluster [T: type] is make, left, right, get_cell, set_cell,

elements, get_size

print_tape(po, t.tap)

end

{{out}}

<pre>Simple incrementer: 1111

# <code>front</code> contains all cells before the current cell in reverse order (i.e. the first element in <code>front</code> is the direct predecessor of the current cell)

# <code>back</code> contains the current cell as its first element, followed by all successors.

(labels ((combine (front back)

(if front

(when verbose

(show-tape front back))

 

===Recursive version===

Using the same interface and general idea as the iterative version.

(labels ((run (state front back)

(if (equal state terminal)

back)))

 

 

===Usage===

(defun make-rules-table (rules-list)

(let ((rules (make-hash-table :test 'equal)))

(E 1 0 left A)))

'())

 

{{Out}}

5-state busy beaver (first 20 cells)

10100100100100100100...</pre>

=={{header|Cowgol}}==

include "strings.coh";

include "malloc.coh";

print_nl();

i := i + 1;

{{out}}

<pre>Simple incrementer: 1111

===Nearly Strongly Typed Version===

This is typed a little less strongly than the Ada entry. It's fast and safe.

std.exception, std.traits, std.math, std.range;

 

}

M4(tm4);

{{out}}

<pre>Incrementer:

===Simple Version===

While the precedent version is Ada-like, this is more like a script.

 

void turing(Sy, St)(in St state, Sy[int] tape, in int pos,

"b": [0: tuple(1, -1, "a"), 1: tuple(1, 1, "b")],

"c": [0: tuple(1, -1, "b"), 1: tuple(1, 0, "")]]);

{{out}}

<pre>(0)

 

=={{header|Déjà Vu}}==

local :t {}

while /= ) dup:

else:

return paste-together tape-left head tape

 

===Simple incrementer===

 

)

:q0 1 1 :right :q0

:q0 :B 1 :stay :qf

{{out}}

<pre>[ 1 1 1 1 ]</pre>

===Three-state busy beaver===

 

)

:a :B 1 :right :b

:c :B 1 :left :b

:c 1 1 :stay :halt

{{out}}

<pre>[ 1 1 1 1 1 1 ]</pre>

===5-state, 2-symbol probable Busy Beaver machine===

 

)

:A :B 1 :right :B

:E :B 1 :stay :H

:E 1 :B :left :A

 

(Output omitted because of length.)

We define a Turing machine as an instance of TM struct, which stores the definition values (states,symbols,rules) and the current state values (state, tape, position). It can be stopped, restarted, called as a sub-program, or transformed into a sequence or stream.'Huge' TM are run in the background. Rules are compiled into a vector indexed by state * symbol.

=== Turing Machines ===

(require 'struct)

 

(when (= final state) (writeln 'Stopping (TM-name T) 'at-pos (- pos (TM-mem T))))

count)

{{out}}

<pre>

We create a task to run it in the background.

{{out}}

(define steps 0)

(define (TM-task T)

(when (zero? count) (writeln 'END steps (date)))

(if (zero? count) #f T)) ;; return #f to signal end of task

<pre>

;; 5-states 2-symbols busy beaver

 

When running the 5-state busy beaver, the simulator executed 2.7 billion EDSAC orders, which would have taken about 48 days on the original EDSAC. (Cf the estimate of "months" for the same task in ZX81 Basic.)

[Attempt at Turing machine for Rosetta Code.]

[EDSAC program, Initial Orders 2.]

PF [enter with acc = 0]

[end]

{{out}}

<pre>

In this universal Turing machine simulator, a machine is defined by giving it a configuration function that returns the initial state, the halting states and the blank symbol, as well as a function for the rules. These are passed in to the public interface <code>turing/3</code> as funs, together with the initial tape setup.

 

 

-module(turing).

action(stay, _, Tape) -> Tape;

action(right, Blank, {Left, []}) -> {[Blank|Left], []};

 

=={{header|Fortran}}==

 

===Source===

TAPE(HEAD) = MARK(I) !Do it. Possibly not changing the symbol.

HEAD = HEAD + MOVE(I) !Possibly not moving the head.

STATE = ICHAR(NEXT(I)) !Hopefully, something has changed!

Which manifests the ability to read and write memory, simple arithmetic, and a conditional branch. This is all it takes. And thanks to Kurt Gödel, it is known that simple arithmetic is enough to construct statements that are true, but unprovable.

 

The use of ICHAR() and CHAR() hopefully involves no machine code effort, they are merely a genuflection to the rules of type checking to calm the compiler. Most of the blather is concerned with acquiring the description (with minimal checking), and preparing some trace output.

 

Careful! Reserves a symbol #0 to represent blank tape as a blank.

INTEGER MANY,FIRST,LAST !Some sizes must be decided upon.

END DO !On to the next symbol in the order as supplied.

END DO !And the next state, in numbers order.

 

===Results===

=={{header|Fōrmulæ}}==

 

 

 

 

=={{header|Go}}==

 

type Symbol byte

m.state = act.next

}

An example program using the above package:

 

import (

fmt.Println("Turing machine halts after", cnt, "operations")

fmt.Println("Resulting tape:", output)

{{out}}

<pre>Turing machine halts after 4 operations

In this program the tape is infinite, and the machines rules are coded in Haskell as a function from state and value to action, using Haskell as a DSL.

 

data Move = MLeft | MRight | Stay deriving (Show, Eq)

data Tape a = Tape a [a] [a]

runUTM rules stop start tape = steps ++ [final]

where (steps, final:_) = break ((== stop) . fst) $ iterate (step rules) (start, tape)

 

====Increment machine====

incr "q0" 0 = Action 1 Stay "qf"

 

tape1 = tape 0 [] [1,1, 1]

machine1 = runUTM incr "qf" "q0" tape1

 

The output of the increment machine :

("q0",0000000000[1]1100000000)

("q0",0000000001[1]1000000000)

("q0",0000000111[0]0000000000)

("qf",0000000111[1]0000000000)

 

====Beaver machine====

beaver "a" 1 = Action 1 MLeft "c"

beaver "b" 0 = Action 1 MLeft "a"

tape2 = tape 0 [] []

machine2 = runUTM beaver "halt" "a" tape2

 

====Sorting test====

sorting "A" 2 = Action 3 MRight "B"

sorting "A" 0 = Action 0 MLeft "E"

tape3 = tape 0 [] [2,2,2,1,2,2,1,2,1,2,1,2,1,2]

machine3 = runUTM sorting "STOP" "A" tape3

 

===Using State Monad===

Intermediate states can be logged during execution, or they can be discarded. The initial and final states as well as errors are always logged.

Three functions are added so that machines can be written to a file and parsed/run from there. Examples are provided.

import Control.Monad.State

import Data.List (intersperse, nub, find)

, machineLog = []

, machineLogActive = True }

Examples for machine files:

<pre>

This particular UTM halts when entering a final state or when a motion of 'halt' is acted on.

 

record delta(old_state, input_symbol, new_state, output_symbol, direction)

 

write(l,r)

write(repl(" ",*l),"^")

 

First sample machine, with tape changes on each transition traced:

===The universal (stateless point-free) Turing machine===

The universal Turing machine is defined in terms of fixed tacit (stateless point-free) code, showing that this dialect of J is Turing complete.

 

utm=.

 

)

 

===The incrementer machine===

NB. Simple Incrementer...

3 : ^

0 0:1111

 

=== The three-state busy beaver machine===

NB. 0 1 Tape Symbol Scan

NB. S p m g p m g (p,m,g) → (print,move,goto)

12 : ^

2 1:111111

 

=== The probable 5-state, 2-symbol busy beaver machine===

NB. 0 1 Tape Symbol Scan

NB. S p m g p m g (p,m,g) → (print,move,goto)

0 :^

4 0 :101001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001...

 

=== The sorting stress test machine===

NB. 0 1 2 3 Tape Symbol Scan

NB. S p m g p m g p m g p m g (p,m,g) ➜ (print,move,goto)

100: ^

4 0:0111111222222220

 

=== The structured derivation of the universal Turing machine ===

The fixed tacit code was produced by means of an unorthodox tacit toolkit; however, the verb produced is orthodox (i.e., compliant with the language specifications):

 

 

NB.--------------------------------------------------------------------------------------

utm=. utm f. NB. Fixing the universal Turing machine code

 

 

=={{header|Java}}==

This is an implementation of the universal Turing machine in plain Java using standard libraries only. As generics are used, Java 5 is required. The examples (incrementer and busy beaver) are implemented directly in the main method and executed sequentially; as an additional third example, a sorting algorithm is implemented and executed in the end of the main method. During execution the complete tape and the current active transition are printed out in every step. The state names and tape symbols may contain several characters, so arbitrary strings such as "q1", "q2", ... can be valid state names or tape symbols. The machine is deterministic as the transitions are stored in a HashMap which uses state / tape symbol pairs as keys. This is self-coded, not a standard implementation, so there is no guarantee of correctness.

 

import java.util.HashSet;

import java.util.LinkedList;

System.out.println("Output (sort): " + machine.runTM() + "\n");

}

 

{{out}} -- [H] denotes the head; its position on the tape is over the symbol printed right from it.

=={{header|JavaScript}}==

{{works with|FireFox}}

document.write(d, '<br>')

if (i<0||i>=t.length) return

'3.0: 1, L, 3',

'3.1: 1, L, 1'

{{out}}

Unary incrementer<br>&nbsp;&nbsp;*: a [<u>1</u>11]<br>&nbsp;&nbsp;1: a [<u>&nbsp;</u>111]<br>&nbsp;&nbsp;2: h [<u>1</u>111]<br> <br>Unary adder<br>&nbsp;&nbsp; *: 1 [<u>1</u>11&nbsp;111]<br> &nbsp;&nbsp;1: 2 [&nbsp;<u>1</u>1&nbsp;111]<br> &nbsp;&nbsp;2: 3 [&nbsp;1<u>1</u>&nbsp;111]<br> &nbsp;&nbsp;3: 3 [&nbsp;11<u>&nbsp;</u>111]<br> &nbsp;&nbsp;4: 0 [&nbsp;11<u>1</u>111]<br> <br>Three-state busy beaver<br>&nbsp;&nbsp; *: 1 [<u>&nbsp;</u>]<br> &nbsp;&nbsp;1: 2 [1<u>&nbsp;</u>]<br> &nbsp;&nbsp;2: 3 [1&nbsp;<u>&nbsp;</u>]<br> &nbsp;&nbsp;3: 3 [1<u>&nbsp;</u>1]<br> &nbsp;&nbsp;4: 3 [<u>1</u>11]<br> &nbsp;&nbsp;5: 1 [<u>&nbsp;</u>111]<br> &nbsp;&nbsp;6: 2 [1<u>1</u>11]<br> &nbsp;&nbsp;7: 2 [11<u>1</u>1]<br> &nbsp;&nbsp;8: 2 [111<u>1</u>]<br> &nbsp;&nbsp;9: 2 [1111<u>&nbsp;</u>]<br> &nbsp;10: 3 [1111&nbsp;<u>&nbsp;</u>]<br> &nbsp;11: 3 [1111<u>&nbsp;</u>1]<br> &nbsp;12: 3 [111<u>1</u>11]<br> &nbsp;13: 1 [11<u>1</u>111]<br> &nbsp;14: 0 [111<u>1</u>11]

 

=={{header|Julia}}==

 

@enum Move Left=1 Stay Right

turing(prog, tape, verbose)

end

<pre>

Simple incrementer

=={{header|Kotlin}}==

{{trans|C}}

 

enum class Dir { LEFT, RIGHT, STAY }

)

).run()

 

{{out}}

 

=={{header|Lambdatalk}}==

{require lib_H} // associative arrays library

 

output: busy_beaver2: [] -> [1,1,1,1,1,1,1,1,1,1,1]

 

 

=={{header|Lua}}==

local incrementer = {

name = "Simple incrementer",

UTM(incrementer, {"1", "1", "1"})

UTM(threeStateBB, {})

{{out}}

<pre>

 

Steps taken: 47176870</pre>

 

=={{header|Mathematica}}/{{header|Wolfram Language}}==

Updated to use dynamic definition of a function. Values computed for each input are saved.

Functionally equivalent to computing a matrix for a set of inputs.

left = 1; right = -1; stay = 0;

cmp[s_] := ToExpression[StringSplit[s, ","]];

]; {tape, rh}

];

 

===A print routine and test drivers===

 

printMachine[tape_,pos_]:=(mach=IntegerString[tape,2];

ptr=StringReplace[mach,{"0"-> " ","1"->" "}];

fin=utm[Map[cmp,busyBeaver3S],0,0];

printMachine[fin[[1]],fin[[2]]];

 

Summary output from the 2 short machines

Runs in 4 minutes on an i5 desktop (with the dynamic function definiton).

The resulting tape is very long, we'll print the result of treating the value as a binary encoded integer.

probable5S={

"A, 0, 1, right, B",

 

fin[[1]]//N

 

=={{header|MATLAB}}==

%"rules" is cell array of cell arrays of the following form:

%First element is number representing initial state

end

end

{{out}}

<pre>

===The universal machine===

Source for this example was lightly adapted from [https://bitbucket.org/ttmrichter/turing https://bitbucket.org/ttmrichter/turing]. Of particular interest in this implementation is that because of the type parameterisation of the <code>config</code> type, the machine being simulated cannot be compiled if there is any mistake in the states, symbols and actions. Also, because of Mercury's determinism detection and enforcement, it's impossible to pass in a non-deterministic set of rules. At most one answer can come back from the rules interface.

 

:- interface.

action(stay, _, Tape) = Tape.

action(right, Blank, (Left-[])) = ([Blank|Left]-[]).

 

===The incrementer machine===

This machine has been stripped of the Mercury ceremony around modules, imports, etc.

:- type incrementer_symbols ---> b ; '1'.

 

incrementer(a, b, '1', stay, halt).

 

This will, on execution, fill TapeOut with [1, 1, 1, 1].

===The busy beaver machine===

This machine has been stripped of the Mercury ceremony around modules, imports, etc.

:- type busy_beaver_symbols ---> '0' ; '1'.

 

busy_beaver(c, '1', '1', stay, halt).

 

This will, on execution, fill TapeOut with [1, 1, 1, 1, 1, 1].

 

This page also has other information, screen shots, etc.

 

;; "A Turing Turtle": a Turing Machine implemented in NetLogo

;; by Dan Dewey 1/16/2016

 

end

 

=={{header|Nim}}==

{{trans|Python}}

 

proc runUTM(state, halt, blank: string, tape: seq[string] = @[],

"D 3 1 right A".splitWhitespace,

"E 1 1 left E".splitWhitespace,

 

{{out}}

 

=={{header|Perl}}==

use warnings;

 

[qw/D 3 1 right A/],

[qw/E 1 1 left E/],

 

=={{header|Phix}}==

{{trans|Lua}}

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #008080;">enum</span> <span style="color: #000000;">name</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">initState</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">endState</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">blank</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">rules</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>

<span style="color: #0000FF;">?</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)</span>

{{Out}}

<pre>

=={{header|PHL}}==

 

 

extern printf;

emulateTuring(rules, 0, 3, tape, 0);

return 0;

 

Output:

 

=={{header|PicoLisp}}==

(de turing (Tape Init Halt Blank Rules Verbose)

(let

(println '1s: (cnt '((X) (= 1 X)) Tape)) )

{{out}}

<pre>"Simple incrementer"

===The universal machine===

Source for this example was lightly adapted from [https://bitbucket.org/ttmrichter/turing https://bitbucket.org/ttmrichter/turing]. This machine, because of Prolog's dynamic nature, has to check its configuration and the rules' compliance to the same at run-time. This is the role of all but the first of the <code>memberchk/2</code> predicates. In addition, calling the user-supplied rules has to be wrapped in a <code>once/1</code> wrapper because there is no way to guarantee in advance that the rules provided are deterministic. (An alternative to doing this is to simply allow <code>perform/5</code> to be non-deterministic or to check for multiple results and report an error on such.)

call(Config, IS, _, _, _, _),

perform(Config, Rules, IS, {[], TapeIn}, {Ls, Rs}),

 

right(L, [], [B|L], [], B).

===The incrementer machine===

IS = q0, % initial state

FS = [qf], % halting states

incrementer(q0, b, 1, stay, qf).

 

This will, on execution, fill TapeOut with [1, 1, 1, 1].

===The busy beaver machine===

IS = 'A', % initial state

FS = ['HALT'], % halting states

busy_beaver('C', 1, 1, stay, 'HALT').

 

This will, on execution, fill TapeOut with [1, 1, 1, 1, 1, 1].

 

=={{header|Python}}==

{{trans|Perl}}

 

def run_utm(

)

)

 

=={{header|Racket}}==

 

#lang racket

;;;=============================================================

(match-lambda ['(a b) '(c d e)] ... [x x])

l start))))

 

The resulting Turing Machine is a function that maps the initial tape record to the final one, so that several machines could run one after another or composed as any other functions

 

The simple incrementer:

(define INC

(Turing-Machine #:start 'q0

[q0 1 1 right q0]

[q0 () 1 stay qf]))

<pre>

> (INC '(1 1 1))

 

The incrementer for binary numbers

(define ADD1

(Turing-Machine #:start 'Start

[Add 1 0 left Add]

[Add () 1 stay End]))

<pre>

> (ADD1 '(1 1 0))

 

The busy beaver

(define BEAVER

(Turing-Machine #:start 'a

[c () 1 left b]

[c 1 1 stay halt]))

<pre>

> (BEAVER '(()))

 

The sorting machine

(define SORT

(Turing-Machine #:start 'A

[E 1 1 left E]

[E () () right STOP]))

<pre>

> (SORT '(2 1 2 2 2 1 1))

{{trans|Perl}}

{{works with|Rakudo|2018.03}}

$pos += @tape if $pos < 0;

die "Bad initial position" unless $pos ~~ ^@tape;

[< E 0 0 right STOP >]

];

 

{{out}}

Minimal error checking is done, but if no rule is found to be applicable, an appropriate error message is issued.

===incrementer machine===

state = 'q0' /*the initial Turing machine state. */

term = 'qf' /*a state that is used for a halt. */

pad=left('', length( word( arg(1),2 ) ) \==1 ) /*padding for rule*/

rule.rules=arg(1); say right('rule' rules, 20) "═══►" rule.rules

'''output'''

<pre>

 

===three-state busy beaver===

state = 'a' /*the initial Turing machine state. */

term = 'halt' /*a state that is used for a halt. */

exit /*stick a fork in it, we're all done. */

/*──────────────────────────────────────────────────────────────────────────────────────*/

'''output'''

<pre>

 

===five-state busy beaver===

state = 'A' /*initialize the Turing machine state.*/

term = 'H' /*a state that is used for the halt. */

exit /*stick a fork in it, we're done.*/

/*──────────────────────────────────────────────────────────────────────────────────────*/

'''output'''

<pre>

 

===stress sort===

state = 'A' /*the initial Turing machine state. */

term = 'halt' /*a state that is used for the halt. */

exit /*stick a fork in it, we're all done. */

/*──────────────────────────────────────────────────────────────────────────────────────*/

'''output'''

<pre>

=={{header|Ruby}}==

===The universal machine===

class Tape

def initialize(symbols, blank, starting_tape)

return @tape.get_tape

end

 

===The incrementer machine===

:q0 => { 1 => [1, :right, :q0],

:b => [1, :stay, :qf]}

incrementer_rules, # operating rules

[1, 1, 1]) # starting tape

 

===The busy beaver machine===

:a => { 0 => [1, :right, :b],

1 => [1, :left, :c]},

busy_beaver_rules, # operating rules

[]) # starting tape

 

=={{header|Rust}}==

use std::fmt::{Display, Formatter, Result};

 

}

}

{{out}}

<pre>

A simple implementation of Universal Turing Machine in Scala:

 

package utm.scala

 

}

 

{{output}}

<pre>

{{works with|Chez Scheme}}

'''The Implementation'''

 

; The tape is a doubly-linked list of "cells". Each cell is a pair in which the cdr points

((N) head)))))))

 

'''Test Runner'''

 

; Run specified tests: A caption string, a Turing machine, a list of tests, and options (if

(loop (cdr tests)))))))

 

'''The Task'''

"Simple incrementer"

(make-turing

(list

(list 0 #f (make-tape '(0)))

{{out}}

<pre style="height: 75ex; overflow: scroll">

</pre>

'''More Examples'''

"Sorting test"

(make-turing

(list 0 #f (make-tape '(1 1 2 2 1 1)))

(list 0 #f (make-tape '(1 1 2 2 1 2)))

{{out}}

<pre style="height: 107ex; overflow: scroll">

This implemetnation is based on the Computing Machines introduced in Turing's 1936 paper [https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf ON COMPUTABLE NUMBERS, WITH AN APPLICATION TO THE ENTSCHEIDUNGSPROBLEM]. With the exception of "skeleton tables".<br>

'''SequenceL Code:'''<br>

 

import <Utilities/Conversion.sl>;

(CurrentConfig: mConfig.FinalConfig, CurrentPosition: newState.CurrentPosition, Tape: newState.Tape);

 

 

'''C++ Driver Code:'''<br>

#include <fstream>

#include <string>

}

throw(errno);

 

'''Turing Machine Files'''<br />

=={{header|Sidef}}==

{{trans|Raku}}

 

if (pos < 0) {

%w(E 1 1 left E),

%w(E 0 0 right STOP),

 

=={{header|Standard ML}}==

 

 

 

signature TAPE = sig

val () = simulate_int sorting NONE

end

 

{{output}}

 

=={{header|Tcl}}==

set state $initial

set idx 0

}

return [join $tape ""]

Demonstrating:

puts TAPE=[turing {q0 qf} q0 qf {1 B} B "111" {

{q0 1 1 right q0}

{E 1 1 left E}

{E 0 0 right H}

{{out}}

<pre>

=={{header|UNIX Shell}}==

{{works with|Bourne Again Shell|4+}}

main() {

printf 'Simple Incrementer\n'

 

main "$@"

{{Output}}

<pre>Simple Incrementer

 

=={{header|VBA}}==

Public Enum sett

name_ = 1

Set tap = New Collection

UTM fiveStateBB, tap, countOnly:=-1

<pre>Simple incrementer

==================

{{libheader|Wren-dynamic}}

{{libheader|Wren-fmt}}

 

var Dir = Enum.create("Dir", ["LEFT", "RIGHT", "STAY"])

Rule.new("E", "1", "0", Dir.LEFT, "A")

]

 

{{out}}

=={{header|Yabasic}}==

{{trans|Lua}}

 

name = 1 : initState = 2 : endState = 3 : blank = 4 : countOnly = true

UTM(incrementer$, "111")

UTM(threeStateBB$, " ")

 

=={{header|zkl}}==

This uses a dictionary/hash to hold the tape, limiting the length to 64k.

{{Trans|D}}

// blank symbol and terminating state(s) are Void

var Lt=-1, Sy=0, Rt=1; // Left, Stay, Right

tape[pos]=r[0];

return(self.fcn(r[2],tape,pos+r[1],rules,verbose,n+1));

D is a dictionary, SD is a small fixed (at runtime) dictionary

turing("q0",D(0,Rt, 1,Rt, 2,Rt),0, // Incrementer

D("q0",D(1,T(1,Rt,"q0"), Void,T(1,Sy,Void)) ) );

"C",D(Void,T(1,Rt,"D"), 1,T(Void,Lt,"E")),

"D",D(Void,T(1,Lt,"A"), 1,T(1, Lt,"D")),

{{out}}

<pre>