Created
March 10, 2015 23:12
-
-
Save morgotth/db6a81566add7a7da52d to your computer and use it in GitHub Desktop.
Turing machine from https://fr.wikipedia.org/wiki/Machine_de_Turing#Exemple
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
➜ ~ python turing.py | |
1) idx=0 on [1, 1] with state=e1 | |
2) idx=1 on [0, 1] with state=e2 | |
3) idx=2 on [0, 1] with state=e2 | |
4) idx=3 on [0, 1, 0] with state=e3 | |
5) idx=2 on [0, 1, 0, 1] with state=e4 | |
6) idx=1 on [0, 1, 0, 1] with state=e5 | |
7) idx=0 on [0, 1, 0, 1] with state=e5 | |
8) idx=1 on [1, 1, 0, 1] with state=e1 | |
9) idx=2 on [1, 0, 0, 1] with state=e2 | |
10) idx=3 on [1, 0, 0, 1] with state=e3 | |
11) idx=4 on [1, 0, 0, 1] with state=e3 | |
12) idx=3 on [1, 0, 0, 1, 1] with state=e4 | |
13) idx=2 on [1, 0, 0, 1, 1] with state=e4 | |
14) idx=1 on [1, 0, 0, 1, 1] with state=e5 | |
15) idx=2 on [1, 1, 0, 1, 1] with state=e1 | |
Final 16) 2 on [1, 1, 0, 1, 1] |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# -*- coding: utf-8 -*- | |
from __future__ import print_function | |
class Ruban(list): | |
def __init__(self, l): | |
super(Ruban, self).__init__(l) | |
def __getitem__(self, i): | |
if len(self) <= i: | |
return 0 | |
else: | |
return super(Ruban, self).__getitem__(i) | |
def __setitem__(self, name, val): | |
if len(self) == name: | |
self.append(val) | |
else: | |
super(Ruban, self).__setitem__(name, val) | |
def e1(l, i): | |
if l[i] == 0: | |
return None, i | |
else: | |
l[i] = 0 | |
return e2, i+1 | |
def e2(l, i): | |
if l[i] == 1: | |
l[i] = 1 | |
return e2, i+1 | |
else: | |
l[i] = 0 | |
return e3, i+1 | |
def e3(l, i): | |
if l[i] == 1: | |
l[i] = 1 | |
return e3, i+1 | |
else: | |
l[i] = 1 | |
return e4, i-1 | |
def e4(l, i): | |
if l[i] == 1: | |
l[i] = 1 | |
return e4, i-1 | |
else: | |
l[i] = 0 | |
return e5, i-1 | |
def e5(l, i): | |
if l[i] == 1: | |
l[i] = 1 | |
return e5, i-1 | |
else: | |
l[i] = 1 | |
return e1, i+1 | |
def main(): | |
l = Ruban([1, 1]) | |
next = e1 | |
i = 0 | |
s = 1 | |
while next is not None: | |
print("%s) idx=%s on %s with state=%s" % (str(s).rjust(2), i, l, next.__name__)) | |
next, i = next(l, i) | |
s+=1 | |
print("Final %s) %s on %s" % (str(s).rjust(2), i, l)) | |
if __name__ == '__main__': | |
main() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment