git @ Cat's Eye Technologies Beturing / rel_1_1_2011_1214
Import of Beturing 1.1 revision 2011.1214 sources (just HTML fixes). Cat's Eye Technologies 12 years ago
1 changed file(s) with 29 addition(s) and 13 deletion(s). Raw diff Collapse all Expand all
+29
-13
doc/beturing.html less more
0 <html>
1 <head><title>Beturing - a Befunge-flavoured Turing machine</title></head>
0 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
1 <!-- encoding: UTF-8 -->
2 <html xmlns="http://www.w3.org/1999/xhtml" lang="en">
3 <head>
4 <meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
5 <title>Beturing - a Befunge-flavoured Turing machine</title>
6 <!-- begin html doc dynamic markup -->
7 <script type="text/javascript" src="/contrib/jquery-1.6.4.min.js"></script>
8 <script type="text/javascript" src="/scripts/documentation.js"></script>
9 <!-- end html doc dynamic markup -->
10 <style type="text/css">
11 td.grey {
12 background: #d0d0d0;
13 }
14 table {
15 align: center;
16 }
17 </style>
18 </head>
219 <body>
320 <h1>Beturing</h1>
421 <h2>a Befunge-flavoured Turing machine</h2>
2946 <p>The state transition diagram is made up of <i>codes</i>. Each code is a
3047 2x2 block of cells in the following form:</p>
3148
32 <center><table border=0 bgcolor=#e0e0e0>
49 <table border="0">
3350 <tr><td><tt>a</tt></td><td><tt>b</tt></td></tr>
3451 <tr><td><tt>&gt;</tt></td><td><tt>/</tt></td></tr>
35 </table></center>
52 </table>
3653
3754 <p>The code head is considered to be over a code when it is over the upper-left cell of it.
3855 The names and meanings of the four parts of the code are as follows:</p>
108125 <p>The positive and negative interpretations of the data head movement and state transition
109126 operators are given below:</p>
110127
111 <center><table border=1>
128 <table border="1">
112129 <tr><th>Symbol</th><th>Positive interpretation</th><th>Negative interpretation</th></tr>
113130 <tr><td><tt>&gt;</tt></td><td>Move right</td><td>Move right</td></tr>
114131 <tr><td><tt>&lt;</tt></td><td>Move left</td><td>Move left</td></tr>
116133 <tr><td><tt>v</tt></td><td>Move down</td><td>Move down</td></tr>
117134 <tr><td><tt>.</tt></td><td>Don't move</td><td>Don't move</td></tr>
118135 <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>
136 <tr><td class="grey"><tt>\</tt></td><td>Move left</td><td>Move down</td></tr>
137 <tr><td class="grey"><tt>|</tt></td><td>Move up</td><td>Move down</td></tr>
138 <tr><td class="grey"><tt>-</tt></td><td>Move left</td><td>Move right</td></tr>
139 <tr><td class="grey"><tt>`</tt></td><td>Move right</td><td>Move up</td></tr>
140 <tr><td class="grey"><tt>'</tt></td><td>Move left</td><td>Move up</td></tr>
124141 <tr><td><tt>@</tt></td><td>Halt</td><td>Halt</td></tr>
125 </table></center>
142 </table>
126143
127144 <p>Note that "x2" in the rules given above means to advance two cells in the given direction;
128145 this is used everywhere for moving the code head because codes are 2x2 cell blocks.</p>
147164 </ul>
148165
149166 <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>.
167 a state transition diagram that is not a planar graph.
152168 A state transition diagram which is a complete 5-vertex graph, for example, is not planar.</p>
153169
154170 <p>This <b>might</b> mean that it is impossible to construct a