% `99 Bottles of Beer' on a Turing Machine

% written 6/97 by Henrik Theiling <henrik@theiling.de>

%% This defines \delta, the transition function.  There are four entries
%% on each line:
%%   CurrentCharacter OldState    NewCharacterOrAction NewState
%%
%% Thus each line defines:
%%   \delta (CurrentCharacter,OldState) = (NewCharacterOrAction, NewState)
%%

% initialise tape with # cr "99" (#)
  #    0      ->    1
  #    1      cr    2
  cr   2      ->    3
  #    3      \9    3
  \9   3      ->    4
  #    4      \9    4
  \9   4      ->    10
  #    10     1000  10
  1000 10     <-    100

% write `bottle' or `bottles':
% check for `1'
  ?    100    ?    105
  \1   100    <-   102
  ?    102    ?    105
  cr   102    cr   120  % write `bottle', not `bottles'

% write `bottles' (first shift back to the left):
  \0   105    ->   105
  \1   105    ->   105
  \2   105    ->   105
  \3   105    ->   105
  \4   105    ->   105
  \5   105    ->   105
  \6   105    ->   105
  \7   105    ->   105
  \8   105    ->   105
  \9   105    ->   105
  ?    105    ->   106
  #    106    b    106
  b    106    ->   107
  #    107    o    107
  o    107    ->   108
  #    108    t    108
  t    108    ->   109
  #    109    t    110
  t    110    ->   111
  #    111    l    111
  l    111    ->   112
  #    112    e    112
  e    112    ->   113
  #    113    s    200

% write `bottle' (first shift back to the left):
  \1   120    ->   120
  cr   120    ->   120
  ?    120    ->   121
  #    121    b    121
  b    121    ->   122
  #    122    o    122
  o    122    ->   123
  #    123    t    123
  t    123    ->   124
  #    124    t    124
  t    124    ->   125
  #    125    l    125
  l    125    ->   126
  #    126    e    200

% return subroutine 1:
  ?    200    <-   200
  1000 200    #    1000
  2000 200    _    2000
  3000 200    _    3000
  5000 200    #    5000
  6000 200    _    6000
  7000 200    cr   7000
  9100 200    #    9100
  9200 200    _    9200
  9300 200    _    9300
  #    200    #    stop

% return subroutine 2:
  ?    210    ->   210
  4000 210    cr   4000
  8000 210    cr   8000
  9000 210    #    9000
  9400 210    cr   9400

%
% This is the main loop:
%
% 1000 is the return state for the first line after `bottle' or `bottles'
% has been written.
  #    1000   ->   1001
  ?    1001   ->   1001
  #    1001   2000 1002
  2000 1002   ->   300   % write `of beer'

  ?    2000   ->   2000
  #    2000   3000 2000
  3000 2000   ->   400   % write `on the wall'

  ?    3000   ->   3000
  #    3000   4000 500   % copy number

  ?    4000   ->   4000
  #    4000   5000 4000
  5000 4000   <-   100   % write `bottle' or `bottles'

  #    5000   ->   5001
  ?    5001   ->