Implementing a Turing machine in Erlang

Question

I have a little project which is very similar to implementing a Turing machine. The essential problem I have is to save the current configuration e.g. the position of the head and further information. Important to me is especially saving up the head position to move him forwards or backwards. What would be the Erlang way to solve this problem?

I'm new to Erlang but as far as I explored OTP the gen_event behavior is suited for this. My thought was to pass over the initial head position and then change it via a handler. But I guess there are more elegant solutions.

Answer 1

In Erlang, as in other functional languages, you must explicitly manage your state yourself. This means that you have to carry it with you and thread it through your code. It IS much easier than it sounds and quickly becomes second nature.

I would personally use a gen_server behaviour rather than a gen_event. It is more specific and will provide you with better support for your machine. The gen_event is more general than you need. IMAO.

The gen_server behaviour, all the behaviours in fact, provide support for managing state. The behaviours provide the basic functionality of the top-level loop, receiving and sending message, and managing state. Plus a lot of extra goodies you will want, even if you don't know it yet.

You interface the gen_server, all the behaviours, by providing call back functions which the behaviour calls when something happens. You give the name of a module and the behaviour expects that module to contain the callbacks. Usually there are a fixed number of callbacks, for example the gen_server has 6, with predefined names that are called at specific times.

For example there is an init/1 callback which is called when the server is started. It does all the specific initialisation and then returns {ok,State}. This is the state you need for your server. The behaviour manages this and threads it through the callbacks and expects a new one in return.

For example when you do a gen_server:call(Server, Message) this will result that in the server a call is made to the handle_call/3 callback with the following arguments and return values:

handle_call(Message, From, State)  --> {reply,Reply,NewState}

Reply is sent back to the caller and NewState is the updated state which is then passed into the next callback.

You can read more about this in the OTP Design Principles and for example the Gen_Server Behaviour and the gen_server module sections of the documentation.

In you case you would let the behaviour be the Turing machine manage the tape, position, etc and you would send commands to it. IMAO agin.

Answer 2

I think implementation depends of your expectation. You can make pure functional implementation of machine state. You can also make pure functional implementation of transition table as function or module. And finally you can anything of it encapsulate in process using OTP behaviors or not.

Let start with symbols. It can be modeled as atoms and you can choose blank one. It can be atom '0'. It can be some fancy name blank. As you wish. We can define it as constant in turing.hrl.

-define(BLANK, '0').

Let continue with tape. One elegant implementation is using well known zip structure. It will be 3-tuple {LEFT, HEAD, RIGHT}.

-module(tape).

-include("turing.hrl").

-export([new/0, read/1, write/2, left/1, right/1, tape2list/1]).

new() -> {[], ?BLANK, []}.

read({_, HEAD, _}) -> HEAD.

write({LEFT, _, RIGHT}, HEAD) -> {LEFT, HEAD, RIGHT}.

left({LEFT, HEAD, []})         -> {[HEAD|LEFT], ?BLANK, []};
left({LEFT, HEAD, [HR|RIGHT]}) -> {[HEAD|LEFT], HR, RIGHT}.

right({[],        HEAD, RIGHT}) -> {[], ?BLANK, [HEAD|RIGHT]};
right({[HL|LEFT], HEAD, RIGHT}) -> {LEFT, HL, [HEAD|RIGHT]}.

tape2list({LEFT, HEAD, RIGHT}) -> lists:reverse(LEFT, [[HEAD]|RIGHT]).

Now we can make machine implementation. Let expect table implemented as function fun(STATE::any(), SYMBOL::any()) -> {NewSTATE::any(), NewSYMBOL::any(), 'left'|'right'} and state of machine in format {STATE, TAPE}. So transition can be modeled as function next/2. Then we need function which determines if some state is accepting state fun(STATE::any()) -> boolean() and then we can provide function for simulating machine as go/3, continue/3 and extended versions go/5 and continue/5 with additional parameter for printing state of machine. Printing function can manage it's own state.

-module(turing_machine).

-export([next/2, continue/5, continue/3, go/3, go/5, print_with_tape/2]).

next({STATE, TAPE}, F) when is_function(F, 2) ->
  {NewSTATE, NewSYMBOL, Dir} = F(STATE, tape:read(TAPE)),
  {NewSTATE, tape:Dir(tape:write(TAPE, NewSYMBOL))}.

continue({S, _} = St, Transition, IsAccepting, Print, PS) when
  is_function(Transition, 2), is_function(IsAccepting, 1), is_function(Print, 2) ->
    case IsAccepting(S) of
    true -> St;
    false ->
      NSt = next(St, Transition),
      continue(NSt, Transition, IsAccepting, Print, Print(NSt, PS))
  end.

print({S, T}, _) ->
  io:format("State: ~p, Head: ~p~n", [S, tape:read(T)]).

print_with_tape({S, T}, _) ->
  io:format("State: ~p, Tape: ~p~n", [S, tape:tape2list(T)]).

continue(St, Transition, IsAccepting) ->
  continue(St, Transition, IsAccepting, fun print/2, ok).

go(IS, Transition, IsAccepting) ->
  go(IS, Transition, IsAccepting, fun print/2, ok).

go(IS, Transition, IsAccepting, Print, PS) ->
  continue({IS, tape:new()}, Transition, IsAccepting, Print, PS).

Then we can make busy beaver machine as function

BB = fun
  ('A', '0') -> {'B', '1', right};
  ('A', '1') -> {'C', '1', left};
  ('B', '0') -> {'A', '1', left};
  ('B', '1') -> {'B', '1', right};
  ('C', '0') -> {'B', '1', left};
  ('C', '1') -> {'HALT', '1', right}
end.

BBA = fun(S) -> S =:= 'HALT' end.

And than run:

> turing_machine:go('A', BB, BBA).
State: 'B', Head: '0'
State: 'A', Head: '1'
State: 'C', Head: '0'
State: 'B', Head: '0'
State: 'A', Head: '0'
State: 'B', Head: '1'
State: 'B', Head: '1'
State: 'B', Head: '1'
State: 'B', Head: '1'
State: 'B', Head: '0'
State: 'A', Head: '1'
State: 'C', Head: '1'
State: 'HALT', Head: '1'
{'HALT',{['1'],'1',['1','1','1','1']}}

Or more fancy:

> turing_machine:go('A', BB, BBA, fun turing_machine:print_with_tape/2, ok).
State: 'B', Tape: [['0'],'1']
State: 'A', Tape: ['1',['1']]
State: 'C', Tape: ['1','1',['0']]
State: 'B', Tape: ['1','1','1',['0']]
State: 'A', Tape: ['1','1','1','1',['0']]
State: 'B', Tape: ['1','1','1',['1'],'1']
State: 'B', Tape: ['1','1',['1'],'1','1']
State: 'B', Tape: ['1',['1'],'1','1','1']
State: 'B', Tape: [['1'],'1','1','1','1']
State: 'B', Tape: [['0'],'1','1','1','1','1']
State: 'A', Tape: ['1',['1'],'1','1','1','1']
State: 'C', Tape: ['1','1',['1'],'1','1','1']
State: 'HALT', Tape: ['1',['1'],'1','1','1','1']
{'HALT',{['1'],'1',['1','1','1','1']}}

If you would prefer working with machines as modules you can define behavior turing_machine by adding callbacks into turing_machine.erl

-callback init_st() -> St::any().

-callback transition(St::any(), Symb::any()) ->
  {NewSt::any(), NewSymb::any(), left|right}.

-callback is_accepting(St::any()) -> boolean().

And also some additional exported functions

-export([go_mod/1, go_mod/3, continue_mod/2, continue_mod/4]).

And their implementations

go_mod(Mod) ->
  go_mod(Mod, fun print/2, ok).

go_mod(Mod, Print, PS) ->
  continue_mod(new_st(Mod:init_st()), Mod, Print, PS).

continue_mod(St, Mod) ->
  continue_mod(St, Mod, fun print/2, ok).

continue_mod(St, Mod, Print, PS) ->
  continue(St, fun Mod:transition/2, fun Mod:is_accepting/1, Print, PS).

And than busy beaver module

-module(busy_beaver).

-behaviour(turing_machine).

-include("turing.hrl").

-define(B, ?BLANK).
-define(P, '1').

-export([init_st/0, transition/2, is_accepting/1]).

init_st() -> 'A'.

transition('A', ?B) -> {'B', ?P, right};
transition('A', ?P) -> {'C', ?P, left};
transition('B', ?B) -> {'A', ?P, left};
transition('B', ?P) -> {'B', ?P, right};
transition('C', ?B) -> {'B', ?P, left};
transition('C', ?P) -> {'HALT', ?P, right}.

is_accepting(St) -> St =:= 'HALT'.

And then it can be used as

> turing_machine:go_mod(busy_beaver).
State: 'B', Head: '0'
State: 'A', Head: '1'
State: 'C', Head: '0'
State: 'B', Head: '0'
State: 'A', Head: '0'
State: 'B', Head: '1'
State: 'B', Head: '1'
State: 'B', Head: '1'
State: 'B', Head: '1'
State: 'B', Head: '0'
State: 'A', Head: '1'
State: 'C', Head: '1'
State: 'HALT', Head: '1'
{'HALT',{['1'],'1',['1','1','1','1']}}

Or even

> turing_machine:go_mod(busy_beaver, fun turing_machine:print_with_tape/2, ok).
State: 'B', Tape: [['0'],'1']
State: 'A', Tape: ['1',['1']]
State: 'C', Tape: ['1','1',['0']]
State: 'B', Tape: ['1','1','1',['0']]
State: 'A', Tape: ['1','1','1','1',['0']]
State: 'B', Tape: ['1','1','1',['1'],'1']
State: 'B', Tape: ['1','1',['1'],'1','1']
State: 'B', Tape: ['1',['1'],'1','1','1']
State: 'B', Tape: [['1'],'1','1','1','1']
State: 'B', Tape: [['0'],'1','1','1','1','1']
State: 'A', Tape: ['1',['1'],'1','1','1','1']
State: 'C', Tape: ['1','1',['1'],'1','1','1']
State: 'HALT', Tape: ['1',['1'],'1','1','1','1']
{'HALT',{['1'],'1',['1','1','1','1']}}

And then you can choose make it processes or OTP workers in one or other way.