-module(turing).
-export([turing/2, demo/0, demo2/0, demo3/0]).

%% tape: {list, index}
%% state: {id, zero-op, one-op}
%% operation: {new-state, 0/1, left/right/stop}

step(Tape, State) ->
  {List, I} = Tape,
  {_, ZeroStep, OneStep} = State,
  case lists:nth(I, List) of
    0 -> handle_state(Tape, ZeroStep);
    1 -> handle_state(Tape, OneStep)
  end.

handle_state(Tape, Operation) ->
  {List, I} = Tape,
  {Before, [_|After]} = lists:split(I - 1, List),
  {Next, X, Op} = Operation,
  NewTape = Before ++ [X] ++ After,
  case Op of
    left -> {next, {NewTape, I - 1}, Next};
    right -> {next, {NewTape, I + 1}, Next};
    stop -> {stop, {NewTape, I}, Next}
  end.

turing(Tape, States) ->
  turing({Tape, 1}, States, 0).

turing(Tape, States, Current) ->
  {Operation, NewTape, NextState} = step(Tape, lists:keyfind(Current, 1, States)),
  io:format("Tape: ~w; next state: ~w~n", [NewTape, NextState]),
  case Operation of
    next -> turing(NewTape, States, NextState); 
    stop -> NewTape
  end.

%% requires at least one 0 after the number
demo() ->                                       % unary inc
  turing([0,0,0,0,1,1,1,0,0,0,0,0],
         [{0, {0, 0, right}, {1, 1, right}},
          {1, {0, 1, stop }, {1, 1, right}}
         ]).

demo2() ->                                      % unary add
  turing([0,1,1,0,1,1,1,0,0,0,0,0],
         [{0, {0, 0, right}, {1, 0, right}},
          {1, {2, 1, right}, {1, 1, right}},
          {2, {0, 0, stop }, {2, 1, right}}
         ]).

%% requires at least one 0 before the number, and 2n+1 zeroes after it
demo3() ->                                      % unary double
  turing([0,1,1,1,0,0,0,0,0,0,0,0],
         [{0, {0, 0, right}, {1, 0, right}},
          {1, {2, 0, right}, {1, 1, right}},
          {2, {4, 1, right}, {3, 1, right}},
          {3, {4, 1, right}, {3, 1, right}},
          {4, {4, 1, left }, {5, 1, left }},
          {5, {6, 0, left }, {5, 1, left }},
          {6, {7, 0, right}, {6, 1, left }},
          {7, {8, 0, right}, {1, 0, right}},
          {8, {0, 0, stop }, {8, 1, right}}
         ]).