git @ Cat's Eye Technologies Beturing / rel_1_1_2005_0623
Import of Beturing 1.1 revision 2005.0623 sources. Cat's Eye Technologies 10 years ago
14 changed file(s) with 179 addition(s) and 41 deletion(s). Raw diff Collapse all Expand all
00 <html>
1 <head><title>Beturing - a Befunge-flavoured Turing(-esque) machine</title></head>
1 <head><title>Beturing - a Befunge-flavoured Turing machine</title></head>
22 <body>
33 <h1>Beturing</h1>
4 <h2>a Befunge-flavoured Turing(-esque) machine</h2>
4 <h2>a Befunge-flavoured Turing machine</h2>
55
6 <p><i>Chris Pressey, June 2005</i></p>
6 <p><i>v1.1, Chris Pressey, June 8 2005</i></p>
77 <!--
8 $Id: beturing.html 8 2005-06-06 22:46:20Z catseye $
8 $Id: beturing.html 16 2005-06-11 03:55:20Z catseye $
99 -->
1010
1111 <h3>Introduction</h3>
8484 <ul>
8585 <li>If the data head movement operator is the special symbol <tt>*</tt>, the following things happen:
8686 <ul>
87 <li>The data head is moved by the positive interpretation of the replacement symbol. (Note that this
88 behaviour is new in version 1.1; no data head movement would occur in the <tt>*</tt> case in v1.0.)</li>
8789 <li>The code head is moved by the positive interpretation (x2) of the state transition operator.</li>
8890 </ul>
8991 </li>
114116 <tr><td><tt>v</tt></td><td>Move down</td><td>Move down</td></tr>
115117 <tr><td><tt>.</tt></td><td>Don't move</td><td>Don't move</td></tr>
116118 <tr><td><tt>/</tt></td><td>Move right</td><td>Move down</td></tr>
119 <tr><td bgcolor=#d0d0d0><tt>\</tt></td><td>Move left</td><td>Move down</td></tr>
120 <tr><td bgcolor=#d0d0d0><tt>|</tt></td><td>Move up</td><td>Move down</td></tr>
121 <tr><td bgcolor=#d0d0d0><tt>-</tt></td><td>Move left</td><td>Move right</td></tr>
122 <tr><td bgcolor=#d0d0d0><tt>`</tt></td><td>Move right</td><td>Move up</td></tr>
123 <tr><td bgcolor=#d0d0d0><tt>'</tt></td><td>Move left</td><td>Move up</td></tr>
117124 <tr><td><tt>@</tt></td><td>Halt</td><td>Halt</td></tr>
118125 </table></center>
119126
123130 <h3>Discussion</h3>
124131
125132 <p>The Beturing language was designed (in part) as a test of the wire-crossing problem,
126 in the following manner.</p>
133 in the following manner. Note these things about Beturing:</p>
127134
128 <p>Note that the code head does not have "direction" or "delta" state as the instruction
129 pointer does in Befunge; it has only "position" state. Its next position (and thus the machine's
130 next state) is determined entirely by the state transition operator of the current code.</p>
135 <ul>
136 <li>Unlike Befunge's instruction pointer, the code head does not have "direction" or
137 "delta" state; it has only "position" state. Its next position (and thus the machine's
138 next state) is determined entirely by the state transition operator of the current code.</li>
131139
132 <p>Note also that there is no "leap over" state transition operator (like <tt>#</tt> in Befunge.)
140 <li>Also unlike Befunge and its <tt>#</tt> instruction,
141 there is no "leap over" state transition operator.
133142 Therefore the next state must always be reachable by a continuous, unbroken
134 path through the playfield.</p>
143 path through the playfield.</li>
135144
136 <p>This means that a Beturing machine is incapable of having a state transition diagram
137 that, when rendered on a 2-dimensional plane, requires that two edges cross.
138 (A state diagram with, e.g., 5 states, and a transition from each state to every other state, appears
139 to have this property (although it would be nice to have a reference to a watertight proof of this...))</p>
145 <li>Lastly, unlike Befunge and its torus, the Beturing playfield is really unbounded in all
146 four directions - there is no wrapping around, making it a true plane.</li>
147 </ul>
148
149 <p>All this added together means that a Beturing machine is incapable of having
150 a state transition diagram that is not a
151 <a href="http://planetmath.org/?op=getobj&from=objects&name=PlanarGraph">planar graph</a>.
152 A state transition diagram which is a complete 5-vertex graph, for example, is not planar.</p>
140153
141154 <p>This <b>might</b> mean that it is impossible to construct a
142 true universal Turing machine in Beturing, <i>if</i> a universal Turing machine
143 requires a state diagram which has edges that cross when rendered in two dimensions.</p>
155 true universal Turing machine in Beturing, <i>if</i> a universal Turing machine
156 requires a state diagram that is not a planar graph.</p>
144157
145 <p>If this were the case (and it may well be) then Beturing would not be Turing-complete,
158 <p>If this were the case then Beturing would not be Turing-complete,
146159 and in fact its level of computational power would probably be difficult to determine.</p>
147160
161 <h3>Update</h3>
162
163 <p>Version 1.0 of the Beturing language, and an interpreter for it written in Lua 5,
164 was released June 6th 2005.</p>
165
166 <p>On June 7th, graue's development of the Archway language, and my
167 sketches for a Smallfuck interpreter in Beturing have both strongly suggested that a
168 universal Turing machine's state diagram can indeed be a planar graph. I'd still
169 like to go ahead and implement the Smallfuck interpreter, though, since (even if it's
170 a foregone conclusion) it would be pretty impressive to see in action.</p>
171
172 <p>On June 8th I added the "data head can move on <tt>*</tt>" semantics for v1.1,
173 in preparation for implementing a Smallfuck interpreter from my sketches. Note that
174 this addition does not constitute an increase in Beturing's computational power, only
175 its expressiveness. It was possible to do the same thing in v1.0, but it required one
176 code per symbol in the alphabet, which was a little excessive.</p>
177
178 <p>On June 10th I added extra "decision" state transition operators (shown with
179 a grey background in the above table) for extra flexibility; there are some planar
180 graphs that can't be rendered in Beturing with just <tt>/</tt>: see the diagram of
181 the Uhing 5-state Busy Beaver machine, for example. As always, you can use the
182 <tt>-o</tt> flag to the interpreter to enforce the v1.0 semantics where these
183 aren't available, if you're a purist.</p>
184
148185 </body></html>
Binary diff not shown
Binary diff not shown
Binary diff not shown
Binary diff not shown
Binary diff not shown
Binary diff not shown
Binary diff not shown
Binary diff not shown
Binary diff not shown
Binary diff not shown
00 ## Trivial Beturing program that swaps a's and b's along a line.
1 ## $Id: example.bet 2 2005-06-06 22:28:23Z catseye $
1 ## $Id: example.bet 14 2005-06-09 03:30:28Z catseye $
22 # D(40, 4)
33 # @(40, 4)
4 .bbab.
4 $bbab$
55 # C(0, 0)
66 # @(0, 0)
7
7 . . . . . .
88 *v*<*<*<*>*v
9 aa ab aa
9 aa .ab . .aa .
1010 >/*>./*^*^</*v
11 bb ba bb
11 bb .ba . .bb .
1212 >/*^./*^*^</*v
13 .. .. ..
13 $$ .$$ . .$$ .
1414 >/*^</*>*^.@*v
15
15 . . .
1616 *@ *^*<*<
0 ## A Beturing translatation of an entry for Tibor Rado's "Busy Beaver"
1 ## game (1962) by G Uhing in 1986.
2 ## $Id$
3 ##
4 ## When given only a blank tape intially, this 5-state, 2-symbol machine
5 ## runs for 2,358,064 iterations.
6 ##
7 ## -0- -1-
8 ## 1 1R2 1RH
9 ## 2 1L3 1R3
10 ## 3 0R5 0L4
11 ## 4 1L3 0L2
12 ## 5 1R4 1R1
13 ##
14 ## We use ' ' for 0 and '$' for 1 in the following.
15 # D(0, -1)
16 1...2...3.....4.5...
17 *v*<*<*<*<*<*<*<*<*<
18 .. ............
19 *v *>*>*>*>*v*^
20 .. ............
21 *v *^*v*<*<*v*^
22 $.. $.. .... $ $..
23 >/*></*>>|*<*><|>\*^
24 $$..$$..$ ....$ $$..
25 >@*^>>*^<>*>*^<v>>*^
26 ..............
27 *^*<*<*<*<*<*<
28 ......$
29 *^*<*<<2
00 #!/usr/local/bin/lua
11 --
2 -- beturing.lua
3 -- A Befunge-flavoured Turing(-esque) machine
2 -- beturing.lua v1.1
3 -- Interpreter for Beturing v1.1
4 -- A Befunge-flavoured Turing machine
45 -- Implemented in Lua 5 by Chris Pressey, June 2005
56 --
67
3637 -- ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
3738 -- OF THE POSSIBILITY OF SUCH DAMAGE.
3839 --
39 -- $Id: beturing.lua 2 2005-06-06 22:28:23Z catseye $
40 -- $Id: beturing.lua 17 2005-06-12 02:37:25Z catseye $
41
42 --
43 -- v1.0: June 6 2005: initial release
44 -- v1.1: June 8 2005: changed semantics of '*' special code
45 --
4046
4147 --[[ Common functions ]]--
4248
4349 local debug_log = print
4450 local usage = function()
45 io.stderr:write("Usage: [lua] beturing.lua [-q] [filename.bet]\n")
51 io.stderr:write("Usage: [lua] beturing.lua [-oq] [-d x1,y1:x2,y2] [filename.bet]\n")
4652 os.exit(1)
4753 end
54 local old_semantics = false
55 local display = nil
4856
4957 --[[ Object Classes ]]--
5058
138146 --
139147 -- Return a string representing the playfield.
140148 --
141 method.render = function(pf)
142 local y = min_y
143 local s = "--- (" .. tostring(min_x) .. "," .. tostring(min_y) .. ")-"
144 s = s .. "(" .. tostring(max_x) .. "," .. tostring(max_y) .. ") ---\n"
145 while y <= max_y do
146 local x = min_x
147 while x <= max_x do
149 method.render = function(pf, start_x, start_y, end_x, end_y)
150 start_x = start_x or min_x
151 start_y = start_y or min_y
152 end_x = end_x or max_x
153 end_y = end_y or max_y
154 local y = start_y
155 local s = "--- (" .. tostring(start_x) .. "," .. tostring(start_y) .. ")-"
156 s = s .. "(" .. tostring(end_x) .. "," .. tostring(end_y) .. ") ---\n"
157 while y <= end_y do
158 local x = start_x
159 while x <= end_x do
148160 s = s .. pf:peek(x, y)
149161 x = x + 1
150162 end
172184 local pf = assert(tab.playfield)
173185 local x = tab.x or 0
174186 local y = tab.y or 0
187 local moves_left = 0
188 local moves_right = 0
175189
176190 local method = {}
191
192 method.report = function(hd)
193 io.stdout:write("Moves left: " .. tostring(moves_left) .. ", moves right: " .. tostring(moves_right) .. "\n")
194 io.stdout:write("Total moves: " .. tostring(moves_left + moves_right) .. "\n")
195 end
177196
178197 method.read = function(hd, sym)
179198 return pf:peek(x, y)
211230 y = y + 1
212231 elseif sym == "<" then
213232 x = x - 1
233 moves_left = moves_left + 1
214234 elseif sym == ">" then
215235 x = x + 1
236 moves_right = moves_right + 1
216237 elseif sym ~= "." then
217238 error("Illegal movement symbol '" .. sym .. "'")
218239 end
253274 local interpret = function(sym, sense)
254275 if sense then
255276 -- Positive interpretation.
256 if sym == "/" then
277 -- Backwards compatibility:
278 if old_semantics then
279 if sym == "/" then
280 return ">"
281 else
282 return sym
283 end
284 end
285 if sym == "/" or sym == "`" then
257286 return ">"
287 elseif sym == "\\" or sym == "'" or sym == "-" then
288 return "<"
289 elseif sym == "|" then
290 return "^"
258291 else
259292 return sym
260293 end
261294 else
262295 -- Negative interpretation.
263 if sym == "/" then
296 -- Backwards compatibility:
297 if old_semantics then
298 if sym == "/" then
299 return "v"
300 else
301 return sym
302 end
303 end
304 if sym == "/" or sym == "\\" or sym == "|" then
264305 return "v"
306 elseif sym == "-" then
307 return ">"
308 elseif sym == "`" or sym == "'" then
309 return "^"
265310 else
266311 return state_cmd
267312 end
286331 --
287332 if move_cmd == "*" then
288333 --
289 -- Special - match anything, do no rewriting or data head
290 -- moving, and advance the state using positive intrepretation.
334 -- Special - match anything, do no rewriting,
335 -- move the data head using the replacement symbol
336 -- (unless using the old compatibility semantics,)
337 -- and advance the state using the positive interpretation.
291338 --
292339 debug_log("-> Wildcard!")
340 if not old_semantics then
341 data_head:move(repl_sym)
342 end
293343 code_move = interpret(state_cmd, true)
294344 elseif seek_sym == this_sym then
295345 --
330380 method.run = function(m)
331381 local done = false
332382 while not done do
333 debug_log(pf:render())
383 if display then
384 io.stdout:write(pf:render(display.x1, display.y1,
385 display.x2, display.y2))
386 else
387 debug_log(pf:render())
388 end
334389 done = not m:step()
335390 end
391 data_head:report()
336392 end
337393
338394 return method
346402
347403 local argno = 1
348404 while arg[argno] and string.find(arg[argno], "^%-") do
349 if arg[argno] == "-q" then
405 if arg[argno] == "-q" then -- quiet
350406 debug_log = function() end
407 elseif arg[argno] == "-o" then -- use v1.0 semantics
408 old_semantics = true
409 elseif arg[argno] == "-d" then
410 argno = argno + 1
411 local found, len
412 display = {}
413 found, len, display.x1, display.y1, display.x2, display.y2 =
414 string.find(arg[argno], "(%-?%d+)%,(%-?%d+)%:(%-?%d+)%,(%-?%d+)")
415 if not found then
416 usage()
417 end
418 display.x1 = tonumber(display.x1)
419 display.y1 = tonumber(display.y1)
420 display.x2 = tonumber(display.x2)
421 display.y2 = tonumber(display.y2)
351422 else
352423 usage()
353424 end