-
Notifications
You must be signed in to change notification settings - Fork 2
/
Copy pathinfo.html
381 lines (372 loc) · 20.9 KB
/
info.html
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
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
<!DOCTYPE html>
<html lang="en-US">
<head>
<meta http-equiv="content-type" content="text/html; charset=UTF-8" />
<meta name="generator" content="Madoko, version 1.0.3" />
<meta name="viewport" content="initial-scale=1.0" />
<meta name="author" content="by [Theresa Fröschl](https://github.com/theresa77) and [Maximilian Irro](https://github.com/mpgirro)" />
<title>Universal Turing Machine in Forth</title>
<style type="text/css" class="link">
/*# sourceURL=madoko.css */
.madoko .toc>.tocblock .tocblock .tocblock {
margin-left: 2.25em;
}
.madoko .toc>.tocblock .tocblock {
margin-left: 1.5em;
}
.madoko .toc-contents>.tocblock>.tocitem {
font-weight: bold;
}
.madoko .toc {
margin-top: 1em;
}
.madoko p.para-continue {
margin-bottom: 0pt;
}
.madoko .para-block+p {
margin-top: 0pt;
}
.madoko ul.para-block, .madoko ol.para-block {
margin-top: 0pt;
margin-bottom: 0pt;
}
.madoko ul.para-end, .madoko ol.para-end {
margin-bottom: 1em;
}
.madoko dl {
margin-left: 0em;
}
.madoko blockquote {
font-style: italic;
}
.madoko a.localref {
text-decoration: none;
}
.madoko a.localref:hover {
text-decoration: underline;
}
.madoko .footnotes {
font-size: smaller;
margin-top: 2em;
}
.madoko .footnotes hr {
width: 50%;
text-align: left;
}
.madoko .footnote {
margin-left: 1em;
}
.madoko .footnote-before {
margin-left: -1em;
width: 1em;
display: inline-block;
}
.madoko .align-center, .madoko .align-center>p {
text-align: center !important;
}
.madoko .align-center pre {
text-align: left;
}
.madoko .align-center>* {
margin-left: auto !important;
margin-right: auto !important;
}
.madoko .align-left, .madoko .align-left>p {
text-align: left !important;
}
.madoko .align-left>* {
margin-left: 0pt !important;
margin-right: auto !important;
}
.madoko .align-right, .madoko .align-right>p {
text-align: right !important;
}
.madoko .align-right>* {
margin-left: auto !important;
margin-right: 0pt !important;
}
.madoko .align-center>table,
.madoko .align-left>table,
.madoko .align-right>table {
text-align: left !important;
}
.madoko .equation-before {
float: right;
}
.madoko .bibitem {
font-size: smaller;
}
.madoko .bibsearch {
font-size: x-small;
text-decoration:none;
color: black;
font-family: "Segoe UI Symbol", Symbola, serif;
}
.madoko .block, .madoko .figure, .madoko .bibitem, .madoko .equation, .madoko div.math {
margin-top: 1ex;
margin-bottom: 1ex;
}
.madoko .figure {
padding: 0.5em;
margin-left: 0pt;
margin-right: 0pt;
}
.madoko .hidden {
display: none;
}
.madoko .invisible {
visibility: hidden;
}
.madoko.preview .invisible {
visibility: visible;
opacity: 0.5;
}
.madoko code.code, .madoko span.code {
white-space: pre-wrap;
}
.madoko hr, hr.madoko {
border: none;
border-bottom: black solid 1px;
margin-bottom: 0.5ex;
}
.madoko .framed>*:first-child {
margin-top: 0pt;
}
.madoko .framed>*:last-child {
margin-bottom: 0pt;
}
.madoko ul.list-style-type-dash {
list-style-type: none !important;
}
.madoko ul.list-style-type-dash > li:before {
content: "\2013";
position: absolute;
margin-left: -1em;
}
.madoko table.madoko {
border-collapse: collapse;
}
.madoko td, .madoko th {
padding: 0ex 0.5ex;
margin: 0pt;
vertical-align: top;
}
.madoko .cell-border-left {
border-left: 1px solid black;
}
.madoko .cell-border-right {
border-right: 1px solid black;
}
.madoko thead>tr:first-child>.cell-line,
.madoko tbody:first-child>tr:first-child>.cell-line {
border-top: 1px solid black;
border-bottom: none;
}
.madoko .cell-line, .madoko .cell-double-line {
border-bottom: 1px solid black;
border-top: none;
}
.madoko .cell-double-line {
border-top: 1px solid black;
padding-top: 1.5px !important;
}
.madoko .input-mathpre .MathJax_Display {
text-align: left !important;
}
.madoko div.input-mathpre {
text-align: left;
margin-top: 1.5ex;
margin-bottom: 1ex;
}
.madoko .math-rendering {
color: gray;
}
.madoko .mathdisplay {
text-align: center;
}
.madoko .pretty table {
border-collapse: collapse;
}
.madoko .pretty td {
padding: 0em;
}
.madoko .pretty td.empty {
min-width: 1.5ex;
}
.madoko .pretty td.expander {
width: 100em;
}
body.madoko, .madoko .serif {
font-family: Cambria,"Times New Roman","Liberation Serif","Times",serif;
}
.madoko .sans-serif {
font-family: "Calibri", "Optima", sans-serif;
}
.madoko .symbol {
font-family: "Segoe UI Symbol", Symbola, serif;
}
body.madoko {
-webkit-text-size-adjust: 100%;
text-rendering: optimizeLegibility;
}
body.madoko {
max-width: 88ex;
margin: 1em auto;
padding: 0em 2em;
}
body.preview.madoko {
padding: 0em 1em;
}
.madoko p {
text-align: justify;
}
.madoko h1, .madoko h2, .madoko h3, .madoko h4 {
margin-top: 1.22em;
margin-bottom: 1ex;
}
.madoko h1+p, .madoko h2+p, .madoko h3+p, .madoko h4+p, .madoko h5+p {
margin-top: 1ex;
}
.madoko h5, .madoko h6 {
margin-top: 1ex;
font-size: 1em;
}
.madoko h5 {
margin-bottom: 0.5ex;
}
.madoko h5 + p {
margin-top: 0.5ex;
}
.madoko h6 {
margin-bottom: 0pt;
}
.madoko h6 + p {
margin-top: 0pt;
}
.madoko pre, .madoko code, .madoko kbd, .madoko samp, .madoko tt,
.madoko .monospace, .madoko .token-indent, .madoko .reveal pre, .madoko .reveal code, .madoko .email {
font-family: Consolas,"Andale Mono WT","Andale Mono",Lucida Console,Monaco,monospace,monospace;
font-size: 0.85em;
}
.madoko pre code, .madoko .token-indent {
font-size: 0.95em;
}
.madoko pre code {
font-family: inherit !important;
}
.madoko ol.linenums li {
background-color: white;
list-style-type: decimal;
}
.madoko .remote {
background-color: #F0FFF0;
}
.madoko .remote + * {
margin-top: 0pt;
}
@media print {
body.madoko {
font-size: 10pt;
}
@page {
margin: 1in 1.5in;
}
}
@media only screen and (max-device-width:1024px) {
body.madoko {
padding: 0em 0.5em;
}
.madoko li {
text-align: left;
}
}
</style>
</head>
<body class="madoko">
<div class="body madoko" style="line-adjust:0">
<div class="titleblock align-center para-block" data-line="4" style="text-align:center;line-adjust:0">
<div class="titleheader align-center" data-line="4" style="text-align:center;line-adjust:0">
<div class="title para-block" data-line="4" style="font-size:xx-large;font-weight:bold;margin-bottom:0.5ex;line-adjust:0"><span data-line="4"></span>Universal Turing Machine in Forth</div></div>
<div class="authors align-center" data-line="9" style="text-align:center;width:80%;line-adjust:0"><table class="authorrow columns block" data-line="9" style="margin-top:2ex;width:100%;line-adjust:0">
<tbody><tr><td class="author column" data-line="9" style="text-align:center;line-adjust:0">
<div class="authorname" data-line="9" style="font-size:large;line-adjust:0"><span data-line="9"></span>by <a href="https://github.com/theresa77">Theresa Fröschl</a> and <a href="https://github.com/mpgirro">Maximilian Irro</a></div></td></tr></tbody></table></div></div>
<p class="p noindent para-continued" data-line="6"><span data-line="6"></span>This is a project for the course<span data-line="6"></span> <a href="http://www.complang.tuwien.ac.at/anton/lvas/stack.html">Stackbasierte Sprachen (2014W)</a><span data-line="6"></span> (german for <span data-line="6"></span><em class="em-star1">stack-based languages</em><span data-line="6"></span>) at<span data-line="6"></span> <a href="http://www.informatik.tuwien.ac.at/english">TU Wien</a><span data-line="6"></span>. The repository is<span data-line="6"></span> <a href="https://github.com/mpgirro/universal-forth-machine">available on GitHub</a><span data-line="6"></span>.
</p>
<p class="p indent" data-line="8"><span data-line="8"></span>We amined to write a Universal Turing Machine using the language Forth. We developed our program for the<span data-line="8"></span> <a href="http://www.complang.tuwien.ac.at/forth/gforth/Docs-html/index.html#Top">Gforth</a><span data-line="8"></span> interpreter. If used with other Forth interpreters there might be issues (we never tested).
</p><h2 id="sec-name-explanation" class="h1" data-line="10" data-heading-depth="1" style="display:block"><span data-line="10"></span><span class="heading-before"><span class="heading-label">1</span>. </span><span data-line="10"></span>Name explanation</h2>
<p class="p noindent" data-line="12"><span data-line="12"></span>We call our program <span data-line="12"></span><em class="em-star1">Universal Forth Machine</em><span data-line="12"></span> (UFM), a wordplay between <span data-line="12"></span>“Universal Turing Machine”<span data-line="12"></span>, being written in Forth, and Forth being a stack machine.
</p><h2 id="sec-usage" class="h1" data-line="14" data-heading-depth="1" style="display:block"><span data-line="14"></span><span class="heading-before"><span class="heading-label">2</span>. </span><span data-line="14"></span>Usage</h2>
<pre class="para-block pre-indented" data-line="16" style="display:block"><code>ufm.forth /path/to/machine /path/to/tape</code></pre><h2 id="sec-machine-specification-format" class="h1" data-line="19" data-heading-depth="1" style="display:block"><span data-line="19"></span><span class="heading-before"><span class="heading-label">3</span>. </span><span data-line="19"></span>Machine specification format</h2>
<p class="p noindent" data-line="21"><span data-line="21"></span>We provide some example machines in<span data-line="21"></span> <a href="machines/">machines/</a><span data-line="21"></span> and tapes to test them in<span data-line="21"></span> <a href="tapes/">tapes/</a><span data-line="21"></span>. The basic file format looks like this:
</p>
<pre class="para-block pre-fenced pre-fenced3" data-line="23" data-line-first="24" style="display:block"><code data-line="24">start-state
state-term1 label
state1
sym-read sym-write next-state tape-ptr-move
sym-read sym-write next-state tape ptr-move
state-term2 otherlabel
state-term3 yetanotherlabel
state2
sym-read sym-write next-state tape-ptr-move
sym-read sym-write next-state tape ptr-move</code></pre>
<p class="p noindent para-continued" data-line="36"><span data-line="36"></span>The first line <span data-line="36"></span><strong class="strong-star2">has</strong><span data-line="36"></span> to be the <span data-line="36"></span><code class="code code1">start-state</code><span data-line="36"></span>. All following lines are state descriptions. A <span data-line="36"></span><code class="code code1">term-state</code><span data-line="36"></span> (terminal state) is followbed by a <span data-line="36"></span><code class="code code1">label</code><span data-line="36"></span> which is a string that will be the output of UFM if the machine terminates in this state. A line containing just a <span data-line="36"></span><code class="code code1">state</code><span data-line="36"></span> token starts the definition of a regular state. All following lines until a new <span data-line="36"></span><code class="code code1">state</code><span data-line="36"></span> or <span data-line="36"></span><code class="code code1">state-term</code><span data-line="36"></span> line are the edge dedinitions for this state. An edge line has to consist of:
</p>
<ol class="ol compact" data-line="38">
<li class="li ol-li compact-li" data-line="38"><span data-line="38"></span><code class="code code1">sym-read</code><span data-line="38"></span>: the symbol read on the tape. If the machine is in the currently defined state, and this symbol is read, the machine will execute the following actions of this line. Think of it as the edge label when picturing the turing machine as a graph.
</li>
<li class="li ol-li compact-li" data-line="39"><span data-line="39"></span><code class="code code1">sym-write</code><span data-line="39"></span>: the symbol to write onto the current tape position.
</li>
<li class="li ol-li compact-li" data-line="40"><span data-line="40"></span><code class="code code1">next-state</code><span data-line="40"></span>: the next state the turing (state-)machine goes to.
</li>
<li class="li ol-li compact-li" data-line="41"><span data-line="41"></span><code class="code code1">tape-ptr-move</code><span data-line="41"></span>: the direction the tape pointer (<span data-line="41"></span><code class="code code1">tape-ptr</code><span data-line="41"></span>) moves. It can go one step to the left (<span data-line="41"></span><code class="code code1">-1</code><span data-line="41"></span>) or right (<span data-line="41"></span><code class="code code1">1</code><span data-line="41"></span>), or just stay (<span data-line="41"></span><code class="code code1">0</code><span data-line="41"></span>) at its current position.
</li></ol>
<p class="p noindent" data-line="43"><span data-line="43"></span><strong class="strong-star2">Note</strong><span data-line="43"></span> that all tokens except the <span data-line="43"></span><code class="code code1">label</code><span data-line="43"></span> for terminal states support literals only! They will all be converted into numbers. So no strings allowed here.
</p><h2 id="sec-special-stack-feature" class="h1" data-line="45" data-heading-depth="1" style="display:block"><span data-line="45"></span><span class="heading-before"><span class="heading-label">4</span>. </span><span data-line="45"></span>Special stack feature</h2>
<p class="p noindent" data-line="47"><span data-line="47"></span>The state transition of the machine is done in a loop calling the <span data-line="47"></span><code class="code code1">transition</code><span data-line="47"></span> word. This is a word that will be dynamically compiled at runtime just before it<span data-line="47"></span>'<span data-line="47"></span>s first execution. Therefore the code of <span data-line="47"></span><code class="code code1">transition</code><span data-line="47"></span> is not hardcoded in the program file, but will be generated by a special compilation word <span data-line="47"></span><code class="code code1">[compile-transition]</code><span data-line="47"></span> which is <span data-line="47"></span><code class="code code1">compile-only</code><span data-line="47"></span> and <span data-line="47"></span><code class="code code1">immediate</code><span data-line="47"></span>. It will compile Forth code into <span data-line="47"></span><code class="code code1">transition</code><span data-line="47"></span> based on the input machine specification file. Have a look at the colon definition of <span data-line="47"></span><code class="code code1">transition</code><span data-line="47"></span> in the source code, and at runtime using <span data-line="47"></span><code class="code code1">see transition</code><span data-line="47"></span>.
</p><h2 id="sec-structure-of-transition-word" class="h1" data-line="49" data-heading-depth="1" style="display:block"><span data-line="49"></span><span class="heading-before"><span class="heading-label">5</span>. </span><span data-line="49"></span>Structure of transition word</h2>
<p class="p noindent" data-line="51"><span data-line="51"></span>The code structure of <span data-line="51"></span><code class="code code1">transition</code><span data-line="51"></span> (which will be compiled depending on the machine-file) looks like this for the<span data-line="51"></span> <a href="machines/increment.machine">machines/increment.machine</a><span data-line="51"></span>:
</p>
<pre class="para-block pre-fenced pre-fenced3 language-forth lang-forth forth" data-line="53" data-line-first="54" style="display:block"><code data-line="54">: transition ( cur-state sym-read -- next-state flag )
over 1 =
IF cr 4546001056 16 type 4545995737 9 type cr 2drop 0 EXIT
THEN
over 0 =
IF dup 1 =
IF 2drop 1 tape-write 0 tape-ptr-move-right -1 EXIT
THEN
dup 0 =
IF 2drop 1 tape-write 1 tape-ptr-move-stay -1 EXIT
THEN
THEN ; ok</code></pre>
<p class="p noindent para-continued" data-line="68"><span data-line="68"></span>The <span data-line="68"></span><code class="code code1">over <some-literal> = if</code><span data-line="68"></span> sequences will check for the state the machine is currently occupying. The <span data-line="68"></span><code class="code code1">dup <some-literal> = if</code><span data-line="68"></span> parts then check the current symbol on the tape. With this mechanism it is decided which action the machine will perform next.
</p><h2 id="sec-resources" class="h1" data-line="70" data-heading-depth="1" style="display:block"><span data-line="70"></span><span class="heading-before"><span class="heading-label">6</span>. </span><span data-line="70"></span>Resources</h2>
<p class="p noindent" data-line="72"><span data-line="72"></span>Program:
</p>
<ul class="ul list-dash compact" data-line="74">
<li class="li ul-li list-dash-li compact-li" data-line="74"><span data-line="74"></span><a href="ufm.forth">ufm.forth</a><span data-line="74"></span>
</li></ul>
<p class="p noindent" data-line="76"><span data-line="76"></span>Machines:
</p>
<ul class="ul list-dash compact" data-line="78">
<li class="li ul-li list-dash-li compact-li" data-line="78"><span data-line="78"></span><a href="machines/increment.machine">increment.machine</a><span data-line="78"></span> <span data-line="78"></span>–<span data-line="78"></span> increment the amount of <span data-line="78"></span><code class="code code1">1</code><span data-line="78"></span>-symbols on the tape by one (at the right edge).
</li>
<li class="li ul-li list-dash-li compact-li" data-line="79"><span data-line="79"></span><a href="machines/multi3.machine">multi3.machine</a><span data-line="79"></span> <span data-line="79"></span>–<span data-line="79"></span> check if tape content holds a multiple of 3 <span data-line="79"></span><code class="code code1">1</code><span data-line="79"></span>-symbols.
</li>
<li class="li ul-li list-dash-li compact-li" data-line="80"><span data-line="80"></span><a href="machines/palindrom.machine">palindrom.machine</a><span data-line="80"></span> <span data-line="80"></span>–<span data-line="80"></span> check if tape content is a palindrom. Border markers are <span data-line="80"></span><code class="code code1">11</code><span data-line="80"></span> (left) and <span data-line="80"></span><code class="code code1">33</code><span data-line="80"></span> (right).
</li></ul>
<p class="p noindent" data-line="82"><span data-line="82"></span>Tapes:
</p>
<ul class="ul list-dash compact" data-line="84">
<li class="li ul-li list-dash-li compact-li" data-line="84"><span data-line="84"></span><a href="tapes/increment.tape">increment.tape</a><span data-line="84"></span>
</li>
<li class="li ul-li list-dash-li compact-li" data-line="85"><span data-line="85"></span><a href="tapes/multi3-yes.tape">multi3-yes.tape</a><span data-line="85"></span> <span data-line="85"></span>–<span data-line="85"></span> the<span data-line="85"></span> <a href="machines/multi3.machine">multi3.machine</a><span data-line="85"></span> should recognize a multiple of 3 <span data-line="85"></span><code class="code code1">1</code><span data-line="85"></span>-symbols.
</li>
<li class="li ul-li list-dash-li compact-li" data-line="86"><span data-line="86"></span><a href="tapes/multi3-no.tape">multi3-no.tape</a><span data-line="86"></span> <span data-line="86"></span>–<span data-line="86"></span> the<span data-line="86"></span> <a href="machines/multi3.machine">multi3.machine</a><span data-line="86"></span> should <span data-line="86"></span><em class="em-star1">not</em><span data-line="86"></span> recognize a multiple of 3 <span data-line="86"></span><code class="code code1">1</code><span data-line="86"></span>-symbols.
</li>
<li class="li ul-li list-dash-li compact-li" data-line="87"><span data-line="87"></span><a href="tapes/palindrom-ok.tape">palindrom-ok.tape</a><span data-line="87"></span> <span data-line="87"></span>–<span data-line="87"></span> the<span data-line="87"></span> <a href="machines/palindrom.machine">palindrom.machine</a><span data-line="87"></span> should accept a palindrom.
</li>
<li class="li ul-li list-dash-li compact-li" data-line="88"><span data-line="88"></span><a href="tapes/palindrom-nok.tape">palindrom-nok.tape</a><span data-line="88"></span> <span data-line="88"></span>–<span data-line="88"></span> the<span data-line="88"></span> <a href="machines/palindrom.machine">palindrom.machine</a><span data-line="88"></span> should <span data-line="88"></span><em class="em-star1">not</em><span data-line="88"></span> accept a palindrom.
</li></ul>
<span data-line=""></span></div>
</body>
</html>