A Turing Machine Simulator Written in Django Template Language

tm.py

import sys, os, re
from django import template
from django.template import loader

TURING_MACHINE = """
{% if not current_state %}
  {% with INITIAL_STATE as current_state %}
    {% with INITIAL_HEAD|default:0|add:1 as pos %}
      {% with "@"|add:TAPE as tape %}
        {% with "TURING_MACHINE" as tm_tpl %}
          {% include tm_tpl %}
        {% endwith %}
      {% endwith %}
    {% endwith %}
  {% endwith %}
{% else %}
  {% for state in ACCEPTING_STATES %}
    {% if current_state == state %}
      accepting {{ state }}: {{ tape|slice:"1:" }}
    {% endif %}
  {% endfor %}
  {% with pos|stringformat:'s'|add:':' as tape_slice %}
    {% with tape|slice:tape_slice|first|default:BLANK_SYMBOL as symbol %}
      {% for state, read, next_state, write, move in TRANSITIONS %}
        {% if state == current_state %}
          {% if read == symbol %}
            state: {{ current_state }}, position: {{ pos|add:-1 }}, 
            tape: {{ tape|slice:"1:" }}, read: {{ symbol }}, 
            write: {{ write }}, move: {{ move }}, next-state: {{ next_state }};
            {% with pos|add:1|stringformat:'s'|add:':' as tail_slice %}
              {% with pos|stringformat:'s' as head_slice %}
                {% with ":"|add:head_slice as head_slice %}
                  {% with tape|slice:tail_slice as tail %}
                    {% with tape|slice:head_slice as head %}
                      {% with head|add:write|add:tail as tape %}
                        {% with pos|add:move as pos %}
                          {% with next_state as current_state %}
                            {% include tm_tpl %}
                          {% endwith %}
                        {% endwith %}
                      {% endwith %}
                    {% endwith %}
                  {% endwith %}
                {% endwith %}
              {% endwith %}
            {% endwith %}
          {% endif %}
        {% endif %}
      {% endfor %}
    {% endwith %}
  {% endwith %}
{% endif %}
"""

if __name__ == '__main__':    
    os.environ['DJANGO_SETTINGS_MODULE'] = os.path.splitext(os.path.basename(__file__))[0]
    loader.template_source_loaders = [lambda name, dirs=None: (TURING_MACHINE, "builtin:TURING_MACHINE")]
    sys.setrecursionlimit(10000) # make the stack larger
    
    L, R = +1, -1
    result = loader.get_template('TURING_MACHINE').render(template.Context({
        'INITIAL_STATE': 'A',
        'ACCEPTING_STATES': ['YES', 'NO'],
        'TAPE': sys.argv[1],
        'INITIAL_HEAD': 0,
        'BLANK_SYMBOL': '_',
        'TRANSITIONS': [
            #state, read, next_state, write, move
            ('A', '0', 'B',   '_', L), # detect 0 - store as state B
            ('A', '1', 'C',   '_', L), # detect 1 - store as state C
            ('A', '_', 'YES', '_', L), # empty string - done (even number) 
            ('B', '1', 'B',   '1', L), # go right
            ('B', '0', 'B',   '0', L),
            ('B', '_', 'D',   '_', R), # end of string detected - go back
            ('C', '1', 'C',   '1', L), # go right
            ('C', '0', 'C',   '0', L),
            ('C', '_', 'E',   '_', R), # end of string detected - go back
            ('D', '0', 'F',   '_', R), # found 0, cancel it - go back 
            ('D', '1', 'NO',  '_', R),
            ('D', '_', 'YES', '_', R), # or found '_' - done (odd number)
            ('E', '0', 'NO',  '_', R),
            ('E', '1', 'F',   '_', R), # found 1, cancel it - go back
            ('E', '_', 'YES', '_', R), # or found '_' - done (odd number)
            ('F', '1', 'F',   '1', R), # go back
            ('F', '0', 'F',   '0', R),
            ('F', '_', 'A',   '_', L), # beginning of string detected
        ],
    }))
    for line in re.sub(" +", " ", result.replace("\n", " ")).split(";"):
        print line.strip()