def turing(band, position, rules):
    """
    A simple turing machine. Special features:
    Use * as a symbol to mean any symbol.
    Use . as a command to specify another turing machine to be executed after the
    new state, using the global variable T to contain such other machines.
    """
    state = "S"
    while True:
        print band
        print position * " " + state

        if state == "H":
            break

        # Lies Symbol vom Band
        try:
            command = rules[state + band[position]]
        except: # if no match, try special * rule
            command = rules[state + "*"]

        # Aktion
        if command[0] == "L": # Links
            position -= 1
            if position < 0:
                band = "#" * -position + band
                position = 0
        elif command[0] == "R": # Rechts
            position += 1
            if position >= len(band):
                band += "#" * (1 + position - len(band))
        elif command[0] == ".": # Rekursiver Aufruf anderer Turingmaschinen
            global T
            others = command[2:].split(",")
            for other in others:
                print "(%s)" % (other)
                band, position = turing(band, position, T[other])
        else: # Schreiben
            band = band[:position] + command[0] + band[position + 1:]

        # neuer Zustand
        state = command[1]
    return band, position

# Beispiel Addierer
adder = {
    "S#" : "Lq",
    "S1" : "1H",
    "q1" : "Lq",
    "q#" : "1p",
    "p1" : "Rp",
    "p#" : "Ls",
    "s1" : "#H"
}

# Kopierer
symbols = ["#", "0", "1"]
copiers = [1, 2, 3]
T = {}

T["L#"] = {
    "S*" : "Lq",
    "q*" : "Lq",
    "q#" : "#H"
}

T["R#"] = {
    "S*" : "Rq",
    "q*" : "Rq",
    "q#" : "#H"
}

# elemental machines
T["L"] = { "S*" : "LH" }
T["R"] = { "S*" : "RH" }

# Wx simply writes x
for s in symbols:
    T["W" + s] = { "S*" : s + "H" }

# Kn copies n items, it uses helpers Tnx
for n in copiers:
    Kn = "K" + str(n)
    T[Kn] = {}
    T[Kn]["S#"] = ".q" + "L#," * n + "R"
    for s in symbols:
        T["T" + str(n) + s] = { "S*" : ".HW#" + ",R#" * (n + 1) +
            ",W" + s + ",L#" * (n + 1) + ",W" + s + ",R" }
        T[Kn]["q" + s] = ".qT" + str(n) + s
    T[Kn]["q#"] = (".H" + "R#," * n)[:-1]

band = "010#11101#1001#"
position = 14

rules = T["K2"]

for rule in rules.items():
    print rule[0], rule[1]
print 
turing(band, position, rules)