Universal Turing machine: Difference between revisions
Content added Content deleted
Line 298: | Line 298: | ||
111111 STOP |
111111 STOP |
||
^</pre> |
^</pre> |
||
=={{header|Erlang}}== |
|||
The following code is an Escript which can be placed into a file and run as <code>escript filename</code> or simply marked as executable and run directly via the provided shebang header. <code>-type</code> and <code>-spec</code> declarations have not been used; using the <code>typer</code> utility can get a head start on this process should a more robust solution be desired. |
|||
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. |
|||
<lang erlang>#!/usr/bin/env escript |
|||
-module(turing). |
|||
-mode(compile). |
|||
-export([main/1]). |
|||
% Incrementer definition: |
|||
% States: a | halt |
|||
% Initial state: a |
|||
% Halting states: halt |
|||
% Symbols: b | '1' |
|||
% Blank symbol: b |
|||
incrementer_config() -> {a, [halt], b}. |
|||
incrementer(a, '1') -> {'1', right, a}; |
|||
incrementer(a, b) -> {'1', stay, halt}. |
|||
% Busy beaver definition: |
|||
% States: a | b | c | halt |
|||
% Initial state: a |
|||
% Halting states: halt |
|||
% Symbols: '0' | '1' |
|||
% Blank symbol: '0' |
|||
busy_beaver_config() -> {a, [halt], '0'}. |
|||
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}. |
|||
% Mainline code. |
|||
main([]) -> |
|||
io:format("==============================~n"), |
|||
io:format("Turing machine simulator test.~n"), |
|||
io:format("==============================~n"), |
|||
Tape2 = turing(fun incrementer_config/0, fun incrementer/2, ['1','1','1']), |
|||
io:format("~w~n", [Tape2]). |
|||
Tape1 = turing(fun busy_beaver_config/0, fun busy_beaver/2, []), |
|||
io:format("~w~n", [Tape1]), |
|||
% Universal Turing machine simulator. |
|||
turing(Config, Rules, Input) -> |
|||
{Start, _, _} = Config(), |
|||
{Left, Right} = perform(Config, Rules, Start, {[], Input}), |
|||
lists:reverse(Left) ++ Right. |
|||
perform(Config, Rules, State, Input = {LeftInput, RightInput}) -> |
|||
{_, Halts, Blank} = Config(), |
|||
case lists:member(State, Halts) of |
|||
true -> Input; |
|||
false -> |
|||
{NewRight, Symbol} = symbol(RightInput, Blank), |
|||
{NewSymbol, Action, NewState} = Rules(State, Symbol), |
|||
NewInput = action(Action, Blank, {LeftInput, [NewSymbol| NewRight]}), |
|||
perform(Config, Rules, NewState, NewInput) |
|||
end. |
|||
symbol([], Blank) -> {[], Blank}; |
|||
symbol([S|R], _) -> {R, S}. |
|||
action(left, Blank, {[], Right}) -> {[], [Blank|Right]}; |
|||
action(left, _, {[L|Ls], Right}) -> {Ls, [L|Right]}; |
|||
action(stay, _, Tape) -> Tape; |
|||
action(right, Blank, {Left, []}) -> {[Blank|Left], []}; |
|||
action(right, _, {Left, [R|Rs]}) -> {[R|Left], Rs}.</lang> |
|||
=={{header|Mercury}}== |
=={{header|Mercury}}== |