Universal Turing machine: Difference between revisions
(Created page with "{{task}} One of the foundational mathematical constructs behind computer science is the [http://en.wikipedia.org/wiki/Universal_Turing_machine universal Turing Machine]. Inde...") |
|||
Line 29: | Line 29: | ||
** (c, 0, 1, left, b). |
** (c, 0, 1, left, b). |
||
** (c, 1, 1, stay, halt). |
** (c, 1, 1, stay, halt). |
||
=={{header|Mercury}}== |
|||
===The universal machine=== |
|||
Source for this example was lightly adapted from [https://bitbucket.org/ttmrichter/turing https://bitbucket.org/ttmrichter/turing]. |
|||
<lang mercury>:- module turing. |
|||
:- interface. |
|||
:- import_module list. |
|||
:- import_module set. |
|||
:- type config(State, Symbol) |
|||
---> config(initial_state :: State, |
|||
halting_states :: set(State), |
|||
blank :: Symbol ). |
|||
:- type action ---> left ; stay ; right. |
|||
:- func turing(config(State, Symbol), |
|||
pred(State, Symbol, Symbol, action, State), |
|||
list(Symbol)) = list(Symbol). |
|||
:- mode turing(in, |
|||
pred(in, in, out, out, out) is semidet, |
|||
in) = out is det. |
|||
:- implementation. |
|||
:- import_module pair. |
|||
:- import_module require. |
|||
turing(Config@config(Start, _, _), Rules, Input) = Output :- |
|||
(Left-Right) = perform(Config, Rules, Start, ([]-Input)), |
|||
Output = append(reverse(Left), Right). |
|||
:- func perform(config(State, Symbol), |
|||
pred(State, Symbol, Symbol, action, State), |
|||
State, pair(list(Symbol))) = pair(list(Symbol)). |
|||
:- mode perform(in, pred(in, in, out, out, out) is semidet, |
|||
in, in) = out is det. |
|||
perform(Config@config(_, Halts, Blank), Rules, State, |
|||
Input@(LeftInput-RightInput)) = Output :- |
|||
symbol(RightInput, Blank, RightNew, Symbol), |
|||
( set.member(State, Halts) -> |
|||
Output = Input |
|||
; Rules(State, Symbol, NewSymbol, Action, NewState) -> |
|||
NewLeft = pair(LeftInput, [NewSymbol|RightNew]), |
|||
NewRight = action(Action, Blank, NewLeft), |
|||
Output = perform(Config, Rules, NewState, NewRight) |
|||
; |
|||
error("an impossible state has apparently become possible") ). |
|||
:- pred symbol(list(Symbol), Symbol, list(Symbol), Symbol). |
|||
:- mode symbol(in, in, out, out) is det. |
|||
symbol([], Blank, [], Blank). |
|||
symbol([Sym|Rem], _, Rem, Sym). |
|||
:- func action(action, State, pair(list(State))) = pair(list(State)). |
|||
action(left, Blank, ([]-Right)) = ([]-[Blank|Right]). |
|||
action(left, _, ([Left|Lefts]-Rights)) = (Lefts-[Left|Rights]). |
|||
action(stay, _, Tape) = Tape. |
|||
action(right, Blank, (Left-[])) = ([Blank|Left]-[]). |
|||
action(right, _, (Left-[Right|Rights])) = ([Right|Left]-Rights).</lang> |
|||
===The incrementer machine=== |
|||
This machine has been stripped of the Mercury ceremony around modules, imports, etc. |
|||
<lang mercury>:- type incrementer_states ---> a ; halt. |
|||
:- type incrementer_symbols ---> b ; '1'. |
|||
:- func incrementer_config = config(incrementer_states, incrementer_symbols). |
|||
incrementer_config = config(a, % the initial state |
|||
set([halt]), % the set of halting states |
|||
b). % the blank symbol |
|||
:- pred incrementer(incrementer_states::in, |
|||
incrementer_symbols::in, |
|||
incrementer_symbols::out, |
|||
action::out, |
|||
incrementer_states::out) is semidet. |
|||
incrementer(a, '1', '1', right, a). |
|||
incrementer(a, b, '1', stay, halt). |
|||
TapeOut = turing(incrementer_config, incrementer, [1, 1, 1]).</lang> |
|||
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. |
|||
<lang mercury>:- type busy_beaver_states ---> a ; b ; c ; halt. |
|||
:- type busy_beaver_symbols ---> '0' ; '1'. |
|||
:- func busy_beaver_config = config(busy_beaver_states, busy_beaver_symbols). |
|||
busy_beaver_config = config(a, % initial state |
|||
set([halt]), % set of terminating states |
|||
'0'). % blank symbol |
|||
:- pred busy_beaver(busy_beaver_states::in, |
|||
busy_beaver_symbols::in, |
|||
busy_beaver_symbols::out, |
|||
action::out, |
|||
busy_beaver_states::out) is semidet. |
|||
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). |
|||
TapeOut = turing(busy_beaver_config, busy_beaver, []).</lang> |
|||
This will, on execution, fill TapeOut with [1, 1, 1, 1, 1, 1]. |
|||
=={{header|Prolog}}== |
=={{header|Prolog}}== |
||
===The universal machine=== |
===The universal machine=== |
||
Source for this example was lightly adapted from [https://bitbucket.org/ttmrichter/turing https://bitbucket.org/ttmrichter/turing]. |
Source for this example was lightly adapted from [https://bitbucket.org/ttmrichter/turing https://bitbucket.org/ttmrichter/turing]. |
||
<lang prolog>turing(Config, Rules, TapeIn, TapeOut) :- |
<lang prolog>turing(Config, Rules, TapeIn, TapeOut) :- |
||
call(Config, IS, _, _, _, _), |
call(Config, IS, _, _, _, _), |
||
Line 66: | Line 186: | ||
===The incrementer machine=== |
===The incrementer machine=== |
||
<lang prolog>incrementer_config(IS, FS, RS, B, S) :- |
<lang prolog>incrementer_config(IS, FS, RS, B, S) :- |
||
IS = q0, % initial state |
IS = q0, % initial state |
||
Line 75: | Line 196: | ||
incrementer(q0, b, 1, stay, qf). |
incrementer(q0, b, 1, stay, qf). |
||
turing(incrementer_config, incrementer, [1, 1, 1], TapeOut). |
turing(incrementer_config, incrementer, [1, 1, 1], TapeOut).</lang> |
||
</lang> |
|||
This will, on execution, fill TapeOut with [1, 1, 1, 1]. |
This will, on execution, fill TapeOut with [1, 1, 1, 1]. |
||
===The busy beaver machine=== |
===The busy beaver machine=== |
||
<lang prolog>busy_beaver_config(IS, FS, RS, B, S) :- |
<lang prolog>busy_beaver_config(IS, FS, RS, B, S) :- |
||
IS = 'A', % initial state |
IS = 'A', % initial state |
Revision as of 07:13, 4 February 2013
You are encouraged to solve this task according to the task description, using any language you may know.
One of the foundational mathematical constructs behind computer science is the universal Turing Machine. Indeed one way to definitively prove that a language is Turing complete is to implement a universal Turing machine in it.
The task
For this task you would simulate such a machine capable of taking the definition of any other Turing machine and executing it. You will not, of course, 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
- States: q0, qf
- Terminating states: qf
- Permissible symbols: B, 1
- Blank symbol: B
- Rules:
- (q0, 1, 1, right, q0)
- (q0, B, 1, stay, qf)
Three-state busy beaver
- States: a, b, c, halt
- Terminating states: halt
- Permissible symbols: 0, 1
- Blank symbol: 0
- Rules:
- (a, 0, 1, right, b).
- (a, 1, 1, left, c).
- (b, 0, 1, left, a).
- (b, 1, 1, right, b).
- (c, 0, 1, left, b).
- (c, 1, 1, stay, halt).
Mercury
The universal machine
Source for this example was lightly adapted from https://bitbucket.org/ttmrichter/turing.
<lang mercury>:- module turing.
- - interface.
- - import_module list.
- - import_module set.
- - type config(State, Symbol)
---> config(initial_state :: State, halting_states :: set(State), blank :: Symbol ).
- - type action ---> left ; stay ; right.
- - func turing(config(State, Symbol),
pred(State, Symbol, Symbol, action, State), list(Symbol)) = list(Symbol).
- - mode turing(in,
pred(in, in, out, out, out) is semidet, in) = out is det.
- - implementation.
- - import_module pair.
- - import_module require.
turing(Config@config(Start, _, _), Rules, Input) = Output :-
(Left-Right) = perform(Config, Rules, Start, ([]-Input)), Output = append(reverse(Left), Right).
- - func perform(config(State, Symbol),
pred(State, Symbol, Symbol, action, State), State, pair(list(Symbol))) = pair(list(Symbol)).
- - mode perform(in, pred(in, in, out, out, out) is semidet,
in, in) = out is det.
perform(Config@config(_, Halts, Blank), Rules, State,
Input@(LeftInput-RightInput)) = Output :- symbol(RightInput, Blank, RightNew, Symbol), ( set.member(State, Halts) -> Output = Input ; Rules(State, Symbol, NewSymbol, Action, NewState) -> NewLeft = pair(LeftInput, [NewSymbol|RightNew]), NewRight = action(Action, Blank, NewLeft), Output = perform(Config, Rules, NewState, NewRight) ; error("an impossible state has apparently become possible") ).
- - pred symbol(list(Symbol), Symbol, list(Symbol), Symbol).
- - mode symbol(in, in, out, out) is det.
symbol([], Blank, [], Blank). symbol([Sym|Rem], _, Rem, Sym).
- - func action(action, State, pair(list(State))) = pair(list(State)).
action(left, Blank, ([]-Right)) = ([]-[Blank|Right]). action(left, _, ([Left|Lefts]-Rights)) = (Lefts-[Left|Rights]). action(stay, _, Tape) = Tape. action(right, Blank, (Left-[])) = ([Blank|Left]-[]). action(right, _, (Left-[Right|Rights])) = ([Right|Left]-Rights).</lang>
The incrementer machine
This machine has been stripped of the Mercury ceremony around modules, imports, etc.
<lang mercury>:- type incrementer_states ---> a ; halt.
- - type incrementer_symbols ---> b ; '1'.
- - func incrementer_config = config(incrementer_states, incrementer_symbols).
incrementer_config = config(a, % the initial state
set([halt]), % the set of halting states b). % the blank symbol
- - pred incrementer(incrementer_states::in,
incrementer_symbols::in, incrementer_symbols::out, action::out, incrementer_states::out) is semidet.
incrementer(a, '1', '1', right, a). incrementer(a, b, '1', stay, halt).
TapeOut = turing(incrementer_config, incrementer, [1, 1, 1]).</lang>
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.
<lang mercury>:- type busy_beaver_states ---> a ; b ; c ; halt.
- - type busy_beaver_symbols ---> '0' ; '1'.
- - func busy_beaver_config = config(busy_beaver_states, busy_beaver_symbols).
busy_beaver_config = config(a, % initial state
set([halt]), % set of terminating states '0'). % blank symbol
- - pred busy_beaver(busy_beaver_states::in,
busy_beaver_symbols::in, busy_beaver_symbols::out, action::out, busy_beaver_states::out) is semidet.
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).
TapeOut = turing(busy_beaver_config, busy_beaver, []).</lang>
This will, on execution, fill TapeOut with [1, 1, 1, 1, 1, 1].
Prolog
The universal machine
Source for this example was lightly adapted from https://bitbucket.org/ttmrichter/turing.
<lang prolog>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, _).</lang>
The incrementer machine
<lang prolog>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).</lang>
This will, on execution, fill TapeOut with [1, 1, 1, 1].
The busy beaver machine
<lang prolog>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).</lang>
This will, on execution, fill TapeOut with [1, 1, 1, 1, 1, 1].