1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154 |
# Incomplete Turing Machine running every possible computation on Python
# read http://en.wikipedia.org/wiki/Dovetailing_%28computer_science%29 and
# http://en.wikipedia.org/wiki/Recursive_enumeration for more information.
# Author: Jose Ignacio Orlicki
# No rights reserved, 2007.
import math
class TuringMachine():
def __init__(self, input):
self.__delta = {}
self.__state = 0
# -1 is caracter b blank
self.__tapes = [input,-1,-1]
self.__tapes_ptr = [0,0,0]
self.__halted = False
def define(self, state, tapes, out_state, out_tapes, move):
if out_tapes[0]==tapes[0] and out_tapes[0]!=-1 and out_tapes[2]!=-1 and moves[0]==+1 and moves[2]==+1:
self.__delta[(state, tapes)] = (out_state, out_tapes, move)
def halted(self):
self.__halted = state==1 and not self.tape_seen()[0]==-1
return self._halted
def tape_seen(self):
return [self.__tapes[0][self._tapes_ptr[0]], self.__tapes[1][self._tapes_ptr[1]], self.__tapes[2][self._tapes_ptr[2]]]
def output(self):
ret = []
for o in self.__tapes[2]:
if o != -1:
ret.append(o)
return ret
def well_formed(self):
well = True
for k in self.__delta.keys():
output_dir = self.__delta(k)[2][2]
well = well and (out_dir==0 or out_dir==1)
return well
def step(self):
try:
self._state, out_tapes, move = self.__delta[self.__state,self.tape_seen()]
except:
self.__halted = True
return
for tape in range(0,3):
if self.__tapes._ptr[tape]==0 and move[tape]==-1:
self.__tapes[tape] = [-1] + self._tapes[tape]
self.__tapes_ptr += 1
if self.__tapes._ptr[tape]==len(self._tapes[tape])-1 and move[tape]==+1:
self.__tapes[tape] = self._tapes[tapes] + [-1]
self.__tapes[tape] = out_tape[tape]
self.__tapes_ptr[tape] += move[tape]
def l(nat):
# TODO
return 0
def r(nat):
# TODO
return 0
def list2str(list_):
ret = ''
for n in list_:
ret.append(chr(n+45))
return ret
def str2list(strn):
ret = []
for c in strn:
ret.append(int(c))
return ret
def int2list(n):
ret = []
while n != 0:
ret.append(n%2)
n = n>>1
return ret
def DoveTailer():
def __init__(self, output):
self.machs = []
self.machs_halted = []
self.machs_output = []
self.n = 0
self.output = str2list(output)
self.min_input = str2list(output)
self.prob = 0.0
self.print_period = 1000
pass
def step(self):
"""the pairing(i,j) step includes running step j of the i machine"""
self.n = 0
self.i = l(self.n)
self.j = r(self.n)
self.n = self.n + 1
if n % self.print_period == 0:
print 'step %d output %s probability %s min_input %s' % (self.n, list2str(self.output), str(self.prob), list2str(self.min_input))
if i==0:
new_mach = len(self.machs) + 1
turing = TuringMachine()
instr_list = new_mach
while instr_list != 0:
instr = l(instr_list)
# ( l, ( rl, ( rrl, ( rrrl, rrrr ) ) ) )
state = l(instr)
tapes = [l(r(instr))-1, l(r(r(instr)))-1, l(r(r(r(instr))))-1 ]
out_state = l(r(r(r(r(instr)))))
out_tapes = [l(r(r(r(r(r(instr))))))-1, l(r(r(r(r(r(r(instr)))))))-1, l(r(r(r(r(r(r(r(instr))))))))-1 ]
moves = [l(r(r(r(r(r(r(r(r(instr)))))))))-1, l(r(r(r(r(r(r(r(r(r(instr))))))))))-1, l(r(r(r(r(r(r(r(r(r(r(instr)))))))))))-1 ]
turing.define(state, tapes, out_state, out_tapes, moves)
instr_list = r(instr_list)
if new_mach.well_formed():
self.machs.append(new_mach)
self.machs_halted.append(False)
self.machs_output.append([])
i = i % len(self.machs)
if self.machs_halted[i]==False and self.machs[i].halted():
self.machs_halted[i] = True
self.machs_output[i] = self.machs[i].output()
if self.machs_output[i] == self.output:
# prefix-free coding of machine numbering
input_as_list = [0]*len(int2list(i)) + [1] + int2list(i)
self.prob += 1/(2^len(input_as_list))
if len(input_as_list) < len(self.min_input):
self.min_input = input_as_list
else:
self.machs[i].step()
def run_steps(self, steps):
while self.n < steps:
self.step()
def run(self):
while True:
self.step()
|
