1. Cat's Eye Technologies
  2. Beturing

Commits

Cat's Eye Technologies  committed 64d5e80

Import of Beturing 1.1 revision 2005.0623 sources.

  • Participants
  • Parent commits 00c58bb
  • Branches default
  • Tags rel_1_1_2005_0623

Comments (0)

Files changed (14)

File doc/beturing.html

View file
 <html>
-<head><title>Beturing - a Befunge-flavoured Turing(-esque) machine</title></head>
+<head><title>Beturing - a Befunge-flavoured Turing machine</title></head>
 <body>
 <h1>Beturing</h1>
-<h2>a Befunge-flavoured Turing(-esque) machine</h2>
+<h2>a Befunge-flavoured Turing machine</h2>
 
-<p><i>Chris Pressey, June 2005</i></p>
+<p><i>v1.1, Chris Pressey, June 8 2005</i></p>
 <!--
-$Id: beturing.html 8 2005-06-06 22:46:20Z catseye $
+$Id: beturing.html 16 2005-06-11 03:55:20Z catseye $
 -->
 
 <h3>Introduction</h3>
 <ul>
 <li>If the data head movement operator is the special symbol <tt>*</tt>, the following things happen:
   <ul>
+  <li>The data head is moved by the positive interpretation of the replacement symbol.  (Note that this
+  behaviour is new in version 1.1; no data head movement would occur in the <tt>*</tt> case in v1.0.)</li>
   <li>The code head is moved by the positive interpretation (x2) of the state transition operator.</li>
   </ul>
 </li>
 <tr><td><tt>v</tt></td><td>Move down</td><td>Move down</td></tr>
 <tr><td><tt>.</tt></td><td>Don't move</td><td>Don't move</td></tr>
 <tr><td><tt>/</tt></td><td>Move right</td><td>Move down</td></tr>
+<tr><td bgcolor=#d0d0d0><tt>\</tt></td><td>Move left</td><td>Move down</td></tr>
+<tr><td bgcolor=#d0d0d0><tt>|</tt></td><td>Move up</td><td>Move down</td></tr>
+<tr><td bgcolor=#d0d0d0><tt>-</tt></td><td>Move left</td><td>Move right</td></tr>
+<tr><td bgcolor=#d0d0d0><tt>`</tt></td><td>Move right</td><td>Move up</td></tr>
+<tr><td bgcolor=#d0d0d0><tt>'</tt></td><td>Move left</td><td>Move up</td></tr>
 <tr><td><tt>@</tt></td><td>Halt</td><td>Halt</td></tr>
 </table></center>
 
 <h3>Discussion</h3>
 
 <p>The Beturing language was designed (in part) as a test of the wire-crossing problem,
-in the following manner.</p>
+in the following manner.  Note these things about Beturing:</p>
 
-<p>Note that the code head does not have "direction" or "delta" state as the instruction
-pointer does in Befunge; it has only "position" state.  Its next position (and thus the machine's
-next state) is determined entirely by the state transition operator of the current code.</p>
+<ul>
+<li>Unlike Befunge's instruction pointer, the code head does not have "direction" or
+"delta" state; it has only "position" state.  Its next position (and thus the machine's
+next state) is determined entirely by the state transition operator of the current code.</li>
 
-<p>Note also that there is no "leap over" state transition operator (like <tt>#</tt> in Befunge.)
+<li>Also unlike Befunge and its <tt>#</tt> instruction,
+there is no "leap over" state transition operator.
 Therefore the next state must always be reachable by a continuous, unbroken
-path through the playfield.</p>
+path through the playfield.</li>
 
-<p>This means that a Beturing machine is incapable of having a state transition diagram
-that, when rendered on a 2-dimensional plane, requires that two edges cross.
-(A state diagram with, e.g., 5 states, and a transition from each state to every other state, appears
-to have this property (although it would be nice to have a reference to a watertight proof of this...))</p>
+<li>Lastly, unlike Befunge and its torus, the Beturing playfield is really unbounded in all
+four directions - there is no wrapping around, making it a true plane.</li>
+</ul>
+
+<p>All this added together means that a Beturing machine is incapable of having
+a state transition diagram that is not a
+<a href="http://planetmath.org/?op=getobj&from=objects&name=PlanarGraph">planar graph</a>.
+A state transition diagram which is a complete 5-vertex graph, for example, is not planar.</p>
 
 <p>This <b>might</b> mean that it is impossible to construct a
-true universal Turing machine in Beturing, <i>if</i> a  universal Turing machine
-requires a state diagram which has edges that cross when rendered in two dimensions.</p>
+true universal Turing machine in Beturing, <i>if</i> a universal Turing machine
+requires a state diagram that is not a planar graph.</p>
 
-<p>If this were the case (and it may well be) then Beturing would not be Turing-complete,
+<p>If this were the case then Beturing would not be Turing-complete,
 and in fact its level of computational power would probably be difficult to determine.</p>
 
+<h3>Update</h3>
+
+<p>Version 1.0 of the Beturing language, and an interpreter for it written in Lua 5,
+was released June 6th 2005.</p>
+
+<p>On June 7th, graue's development of the Archway language, and my
+sketches for a Smallfuck interpreter in Beturing have both strongly suggested that a
+universal Turing machine's state diagram can indeed be a planar graph.  I'd still
+like to go ahead and implement the Smallfuck interpreter, though, since (even if it's
+a foregone conclusion) it would be pretty impressive to see in action.</p>
+
+<p>On June 8th I added the "data head can move on <tt>*</tt>" semantics for v1.1,
+in preparation for implementing a Smallfuck interpreter from my sketches.  Note that
+this addition does not constitute an increase in Beturing's computational power, only
+its expressiveness.  It was possible to do the same thing in v1.0, but it required one
+code per symbol in the alphabet, which was a little excessive.</p>
+
+<p>On June 10th I added extra "decision" state transition operators (shown with
+a grey background in the above table) for extra flexibility; there are some planar
+graphs that can't be rendered in Beturing with just <tt>/</tt>: see the diagram of
+the Uhing 5-state Busy Beaver machine, for example.  As always, you can use the
+<tt>-o</tt> flag to the interpreter to enforce the v1.0 semantics where these
+aren't available, if you're a purist.</p>
+
 </body></html>

File doc/sf-in-bt-2.dia

Binary file added.

File doc/sf-in-bt-2.png

Added
New image

File doc/sf-in-bt-3.dia

Binary file added.

File doc/sf-in-bt-3.png

Added
New image

File doc/sf-in-bt-4.dia

Binary file added.

File doc/sf-in-bt-4.png

Added
New image

File doc/sf-in-bt.dia

Binary file added.

File doc/sf-in-bt.png

Added
New image

File doc/uhing.dia

Binary file added.

File doc/uhing.png

Added
New image

File eg/example.bet

View file
 ## Trivial Beturing program that swaps a's and b's along a line.
-## $Id: example.bet 2 2005-06-06 22:28:23Z catseye $
+## $Id: example.bet 14 2005-06-09 03:30:28Z catseye $
 # D(40, 4)
 # @(40, 4)
-.bbab.
+$bbab$
 # C(0, 0)
 # @(0, 0)
-
+ . . . . . .
 *v*<*<*<*>*v
-aa  ab    aa
+aa .ab . .aa .
 >/*>./*^*^</*v
-bb  ba    bb
+bb .ba . .bb .
 >/*^./*^*^</*v
-..  ..    ..
+$$ .$$ . .$$ .
 >/*^</*>*^.@*v
-
+         . . .
 *@      *^*<*<

File eg/uhing-bb.bet

View file
+## A Beturing translatation of an entry for Tibor Rado's "Busy Beaver"
+## game (1962) by G Uhing in 1986.
+## $Id$
+##
+## When given only a blank tape intially, this 5-state, 2-symbol machine
+## runs for 2,358,064 iterations.
+##
+##    -0-  -1-
+## 1  1R2  1RH
+## 2  1L3  1R3
+## 3  0R5  0L4
+## 4  1L3  0L2
+## 5  1R4  1R1
+##
+## We use ' ' for 0 and '$' for 1 in the following.
+# D(0, -1)
+1...2...3.....4.5...
+*v*<*<*<*<*<*<*<*<*<
+..      ............
+*v      *>*>*>*>*v*^
+..      ............
+*v      *^*v*<*<*v*^
+ $.. $..  .... $ $..
+>/*></*>>|*<*><|>\*^
+$$..$$..$ ....$ $$..
+>@*^>>*^<>*>*^<v>>*^
+  ..............
+  *^*<*<*<*<*<*<
+  ......$ 
+  *^*<*<<2

File src/beturing.lua

View file
 #!/usr/local/bin/lua
 --
--- beturing.lua
--- A Befunge-flavoured Turing(-esque) machine
+-- beturing.lua v1.1
+-- Interpreter for Beturing v1.1
+-- A Befunge-flavoured Turing machine
 -- Implemented in Lua 5 by Chris Pressey, June 2005
 --
 
 -- ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
 -- OF THE POSSIBILITY OF SUCH DAMAGE. 
 --
--- $Id: beturing.lua 2 2005-06-06 22:28:23Z catseye $
+-- $Id: beturing.lua 17 2005-06-12 02:37:25Z catseye $
+
+--
+-- v1.0: June 6 2005: initial release
+-- v1.1: June 8 2005: changed semantics of '*' special code
+--
 
 --[[ Common functions ]]--
 
 local debug_log = print
 local usage = function()
-    io.stderr:write("Usage: [lua] beturing.lua [-q] [filename.bet]\n")
+    io.stderr:write("Usage: [lua] beturing.lua [-oq] [-d x1,y1:x2,y2] [filename.bet]\n")
     os.exit(1)
 end
+local old_semantics = false
+local display = nil
 
 --[[ Object Classes ]]--
 
     --
     -- Return a string representing the playfield.
     --
-    method.render = function(pf)
-        local y = min_y
-	local s = "--- (" .. tostring(min_x) .. "," .. tostring(min_y) .. ")-"
-	s = s .. "(" .. tostring(max_x) .. "," .. tostring(max_y) .. ") ---\n"
-        while y <= max_y do
-	    local x = min_x
-	    while x <= max_x do
+    method.render = function(pf, start_x, start_y, end_x, end_y)
+	start_x = start_x or min_x
+        start_y = start_y or min_y
+	end_x = end_x or max_x
+	end_y = end_y or max_y
+        local y = start_y
+	local s = "--- (" .. tostring(start_x) .. "," .. tostring(start_y) .. ")-"
+	s = s .. "(" .. tostring(end_x) .. "," .. tostring(end_y) .. ") ---\n"
+        while y <= end_y do
+	    local x = start_x
+	    while x <= end_x do
 	        s = s .. pf:peek(x, y)
 	        x = x + 1
 	    end
     local pf = assert(tab.playfield)
     local x = tab.x or 0
     local y = tab.y or 0
+    local moves_left = 0
+    local moves_right = 0
 
     local method = {}
 
+    method.report = function(hd)
+        io.stdout:write("Moves left:  " .. tostring(moves_left) .. ", moves right: " .. tostring(moves_right) .. "\n")
+	io.stdout:write("Total moves: " .. tostring(moves_left + moves_right) .. "\n")
+    end
+
     method.read = function(hd, sym)
         return pf:peek(x, y)
     end
             y = y + 1
         elseif sym == "<" then
             x = x - 1
+	    moves_left = moves_left + 1
         elseif sym == ">" then
             x = x + 1
+	    moves_right = moves_right + 1
         elseif sym ~= "." then
             error("Illegal movement symbol '" .. sym .. "'")
         end
     local interpret = function(sym, sense)
         if sense then
 	    -- Positive interpretation.
-	    if sym == "/" then
+	    -- Backwards compatibility:
+	    if old_semantics then
+	        if sym == "/" then
+		    return ">"
+		else
+		    return sym
+		end
+	    end
+	    if sym == "/" or sym == "`" then
 		return ">"
+	    elseif sym == "\\" or sym == "'" or sym == "-" then
+		return "<"
+	    elseif sym == "|" then
+		return "^"
 	    else
 	        return sym
 	    end
 	else
 	    -- Negative interpretation.
-	    if sym == "/" then
+	    -- Backwards compatibility:
+	    if old_semantics then
+	        if sym == "/" then
+		    return "v"
+		else
+		    return sym
+		end
+	    end
+	    if sym == "/" or sym == "\\" or sym == "|" then
 		return "v"
+	    elseif sym == "-" then
+		return ">"
+	    elseif sym == "`" or sym == "'" then
+		return "^"
 	    else
 	        return state_cmd
 	    end
 	--
 	if move_cmd == "*" then
 	    --
-	    -- Special - match anything, do no rewriting or data head
-	    -- moving, and advance the state using positive intrepretation.
+	    -- Special - match anything, do no rewriting,
+	    -- move the data head using the replacement symbol
+	    -- (unless using the old compatibility semantics,)
+	    -- and advance the state using the positive interpretation.
 	    --
 	    debug_log("-> Wildcard!")
+	    if not old_semantics then
+	        data_head:move(repl_sym)
+	    end
 	    code_move = interpret(state_cmd, true)
 	elseif seek_sym == this_sym then
 	    --
     method.run = function(m)
 	local done = false
 	while not done do
-	    debug_log(pf:render())
+	    if display then
+		io.stdout:write(pf:render(display.x1, display.y1,
+		                          display.x2, display.y2))
+	    else
+	        debug_log(pf:render())
+	    end
 	    done = not m:step()
 	end
+	data_head:report()
     end
 
     return method
 
 local argno = 1
 while arg[argno] and string.find(arg[argno], "^%-") do
-    if arg[argno] == "-q" then
+    if arg[argno] == "-q" then          -- quiet
         debug_log = function() end
+    elseif arg[argno] == "-o" then      -- use v1.0 semantics
+        old_semantics = true
+    elseif arg[argno] == "-d" then
+        argno = argno + 1
+	local found, len
+	display = {}
+        found, len, display.x1, display.y1, display.x2, display.y2 =
+	    string.find(arg[argno], "(%-?%d+)%,(%-?%d+)%:(%-?%d+)%,(%-?%d+)")
+	if not found then
+	    usage()
+	end
+	display.x1 = tonumber(display.x1)
+	display.y1 = tonumber(display.y1)
+	display.x2 = tonumber(display.x2)
+	display.y2 = tonumber(display.y2)	
     else
         usage()
     end