Has anyone out there written a nice demo of a Turing machine[1] in Forth? It could probably be easily and elegantly done with JVN's finite state machine code, but maybe that's overkill. The demo should be capable of accepting a series of user entered program and showing the results after each cycle. Perhaps it's a standard exercise in an intro CS course to write such a virtual machine.
Krishna
[1] For those like me, who have not much CS background, a Turing machine is the prototype computing machine described by Alan Turing in a 1936 paper. It is a simple state machine with just a few instructions (less than 10), but the Church-Turing assertion states that it can be programmed to carry out any algorithm, i.e. it's equivalent to any digital computer that can be conceived. Hope I got that right :)
> Has anyone out there written a nice demo > of a Turing machine[1] in Forth?
Everything you'll ever need has been written in iForth already :-)
> It could > probably be easily and elegantly done > with JVN's finite state machine code, but > maybe that's overkill.
This is do-able...
> The demo should > be capable of accepting a series of user > entered program and showing the results > after each cycle.
A compiler for a Turing machine should be as hard as a normal compiler? Or do you mean the users write programs in a restricted subset?
Gray might be useful once you have a 'Turing assembler' working.
A program that somwhat approaches what you need is COREWARS (on line I think):
| "As seen in SCIENTIFIC AMERICAN, May 1984"
| This file was compatible with UR/FORTH 1.0X. | Copyright [C] 1986 Laboratory Microsystems, Inc.
| The COREWARS game was described in the "Computer Recreations" | department of the May '84 issue of SCIENTIFIC AMERICAN.
| To compile the REDCODE assembler, MARS interpreter, and example programs, | enter:
| INCLUDE corewars.frt
Or the one I have appended, based on a Scientific American article by the unimitable Mr. Dewdney. It is not portable, I'm afraid, but not hard too follow for an EE.
I also remember a series of articles in the German magazine MC, from the DOS/16bit era. I think it was a contest of sorts. I can not find that source code anymore. (What to do with a box full of 5.25" disks when your computer has no drive for it anymore :-)
-marcel
(* * LANGUAGE : ANS Forth * PROJECT : Forth Environments * DESCRIPTION : Graphic Toy * CATEGORY : Example * AUTHOR : Marcel Hendrix, September 9th 1989 * LAST CHANGE : June 9, 1993, Marcel Hendrix *)
NEEDS -miscutil NEEDS -graphics
REVISION -turmites "ÄÄÄ Turmites Version 1.00 ÄÄÄ"
PRIVATES
DOC Turmite (* This (Turing) Machine consists of a state table that prescribes actions to perform in each state, given two possible input values. The "action" record consists of: - a new state. - a colour. Plot the current pixel with it. - a direction to turn to. Move 1 pixel in this new direction. The colour of this new pixel is the "input value" mentioned above.
Alternatively, the state table can be translated into the brains of a neural network. The reverse is much more useful though.
Further reading: A. K. Dewdney, Computer Recreations, Scientific American, September 1989 *) ENDDOC
0 VALUE CurrentState PRIVATE 0 VALUE Direction PRIVATE
: TURMITE, CREATE \ enter <new state> , <colour> , <angle> , PRIVATE DOES> CurrentState 6 * + \ state GETXY GET-DOT 0<> 1 AND 3 * + \ Input C@+ TO CurrentState C@+ GETXY ROT SET-DOT C@ Direction + 3 AND DUP TO Direction CASE 0 OF 1 0 ENDOF 1 OF 0 1 ENDOF 2 OF -1 0 ENDOF 3 OF 0 -1 ENDOF 0 0 ROT ENDCASE IMOVETO ; PRIVATE
: border ?border IF dimension TO zz gbox dimension 5 + TO zz gbox dimension #100 + TO zz gbox dimension #105 + TO zz gbox ENDIF ; PRIVATE
: DO-IT TEXTMODE? IF GRAPHICS ENDIF CLEAR CurrentState cyan SETCOLOR PUT! CLS border CENTER \ Obstructing turmite is more fun.. BEGIN turmite KEY? UNTIL KEY DROP ;
> Has anyone out there written a nice demo > of a Turing machine[1] in Forth?
I don't know if you'll call it nice, but there is a way to go. I only did some desk planning before giving up in disgust, but there is one. You use the two stack nature of Forth. One stack is for "left" of the tape head and the other for "right" of it. You have to do other stuff like bury the data deeper under the top of the return stack so you don't trip over the working end of it, and if you really want to display things as well you will need to pull things out from under the return stack with analogues of PICK and ROLL. That's what disgusted me - but once you have the arrangement and some supporting words in place, the state changes and tape movements are simple additional keywords; any new Turing Machine is no great problem on top of that base, it's just the base that's disgusting. PML.
> probably be easily and elegantly done > with JVN's finite state machine code, but > maybe that's overkill. The demo should > be capable of accepting a series of user > entered program and showing the results > after each cycle. Perhaps it's a standard > exercise in an intro CS course to write > such a virtual machine.
> Krishna
> [1] For those like me, who have not much CS > background, a Turing machine is the prototype > computing machine described by Alan Turing > in a 1936 paper. It is a simple state > machine with just a few instructions (less > than 10), but the Church-Turing assertion > states that it can be programmed to carry > out any algorithm, i.e. it's equivalent to > any digital computer that can be conceived. > Hope I got that right :)
-- GST+NPT=JOBS
I.e., a Goods and Services Tax (or almost any other broad based production tax), with a Negative Payroll Tax, promotes employment.
"Krishna Myneni" <krishnamyn...@compuserve.com> wrote in message news:3EBC7894.90BE75F5@compuserve.com... > Has anyone out there written a nice demo > of a Turing machine[1] in Forth?
Many moons ago, a group of graduate students at the University of California (Berkeley) Math Dept. had an office phone listed in the Oakland-area phone book as the "Turing Machine Repair Service".
I suppose you called them if you had an "infinite" (really unbounded) ammount of broken tape filling up your house in exponential time.
> Everything you'll ever need has been written in iForth already :-)
Hmmm... Is that a mathematical hypothesis like the Church-Turing thesis? :)
> A compiler for a Turing machine should be as hard as a normal > compiler? Or do you mean the users write programs in a restricted > subset?
I was not thinking in terms of a compiler for a Turing machine, but being able to load a sequence of primitives of the form:
current state, input, instruction, next state
into the virtual Turing machine. The Turing machine, as I understand it, would search this table for a match of its current state and input (from the virtual tape), then execute its basic instruction, transition to the next state, and loop until it reached the halt state.
> Gray might be useful once you have a 'Turing assembler' > working.
Yes, to write an actual compiler for the Turing machine! I've looked at Anton Ertl's Gray parser and it should be useful for such a task. But at the moment I'm just interested in a pedagogical example of a Turing machine.
> A program that somwhat approaches what you need is COREWARS (on > line I think):
> > Has anyone out there written a nice demo > > of a Turing machine[1] in Forth?
> I don't know if you'll call it nice, but there is a way to go. I only did > some desk planning before giving up in disgust, but there is one. You use the > two stack nature of Forth. One stack is for "left" of the tape head and the > other for "right" of it. You have to do other stuff like bury the data deeper > under the top of the return stack so you don't trip over the working end of > it, and if you really want to display things as well you will need to pull > things out from under the return stack with analogues of PICK and ROLL. > That's what disgusted me - but once you have the arrangement and some > supporting words in place, the state changes and tape movements are simple > additional keywords; any new Turing Machine is no great problem on top of > that base, it's just the base that's disgusting. PML.
Your method sounds rather complicated. Why not keep the tape in memory instead of using the stacks?
> Your method sounds rather complicated. Why not keep the tape in memory > instead of using the stacks?
I think you should use memory instead. A series of tape, state, and action primitives (words) could be built easy enough. Forth can become your turning machine.
> Many moons ago, a group of graduate students at the University of > California (Berkeley) Math Dept. had an office phone listed in the > Oakland-area phone book as the "Turing Machine Repair Service".
> Has anyone out there written a nice demo > of a Turing machine[1] in Forth? It could > probably be easily and elegantly done > with JVN's finite state machine code, but > maybe that's overkill. The demo should > be capable of accepting a series of user > entered program and showing the results > after each cycle. Perhaps it's a standard > exercise in an intro CS course to write > such a virtual machine.
It sounds like you would like a Turing simulator. If this is the case, it souldn't be to hard to write one in Forth, or rather, on top of Forth. In Forth you create the language you need to solve a problem. There is no reason why Forth couldn't speak turning machine.
You would need a: *state table *controlling word to start the simulator *tape *variety of accessories (printers, etc.) **optional
> Krishna
> [1] For those like me, who have not much CS > background,
I learned about them through "An Introduction to the Theory of Computation" by Michael Sipser.
> > > Has anyone out there written a nice demo > > > of a Turing machine[1] in Forth?
> > I don't know if you'll call it nice, but there is a way to go. I only did > > some desk planning before giving up in disgust, but there is one. You use the > > two stack nature of Forth. One stack is for "left" of the tape head and the > > other for "right" of it. You have to do other stuff like bury the data deeper > > under the top of the return stack so you don't trip over the working end of > > it, .
. . any new Turing Machine is no great problem on top of
> > that base, it's just the base that's disgusting. PML.
> Your method sounds rather complicated. Why not keep the tape in memory > instead of using the stacks?
It is complicated, at least until it is set up (hence the disgust) - but I was coming at this from the direction of keeping the generality. Doing what you describe is more straightforward for any given platform, just not so generic. PML.
-- GST+NPT=JOBS
I.e., a Goods and Services Tax (or almost any other broad based production tax), with a Negative Payroll Tax, promotes employment.
Krishna Myneni wrote: > I was not thinking in terms of a compiler for a Turing machine, > but being able to load a sequence of primitives of the form:
> current state, input, instruction, next state
> into the virtual Turing machine. The Turing machine, as I understand > it, would search this table for a match of its current state and > input (from the virtual tape), then execute its basic instruction, > transition to the next state, and loop until it reached the halt > state.
I wrote a Turing machine compiler in Forth a long time ago; the application was a busy beaver search program. It compiled the Turing machine to 68k assembler, so the target language wasn't Forth. The TM programs had a limited tape and a limited run-time, since the search of busy beavers is a problem where you have an idea of how many steps you may need.
The program wasn't very cleaver, so I won't post it here. The main operation for a turing machine emulator is however simple:
: <statex:0R|1L> ( p -- p' ) dup c@ IF 0 over c! 1+ <next0> ;THEN 1 over c! 1- <next1> ;
<next0> and <next1> jump to the next state labels, they don't need to return to their caller, that's why I use colorForth's ;THEN to express that.
> ... The main operation for a turing machine emulator is > however simple:
> : <statex:0R|1L> ( p -- p' ) > dup c@ IF 0 over c! 1+ <next0> ;THEN 1 over c! 1- <next1> ;
> <next0> and <next1> jump to the next state labels, they don't need to return > to their caller, that's why I use colorForth's ;THEN to express that.
If p is the current tape position, then the above word would read the bit at the current position, write the inverse of the input bit at the current position, then move left if the input was a 0 or move right if the input was a 1. Is this operation general enough for a Turing machine? I thought the movement direction and the write bit (0, 1, or a blank) should be separate parts of the instruction.
In article <3EBC7894.90BE7...@compuserve.com>, Krishna Myneni <krishnamyn...@compuserve.com> wrote:
>Has anyone out there written a nice demo >of a Turing machine[1] in Forth? It could >probably be easily and elegantly done >with JVN's finite state machine code, but >maybe that's overkill. The demo should >be capable of accepting a series of user >entered program and showing the results >after each cycle. Perhaps it's a standard >exercise in an intro CS course to write >such a virtual machine.
This is a bit of a strange request. I think you confuse Turing machines, and the concept of a universal Turing machine.
Turing machines are more like hardware electronics than a stored program computer. It was a non trivial exercise to show that after considerable tweaking and mathematical constructions some of these Turing machines could be interpreted as being a stored program computer.
Writing an interpreter for a hardwired Turing machine is extremely simple in Forth. You need some CARDS, for "a" turing machine these are fixed. On a CARD there are a few basic commands, among them a reference to the next card to be executed, for each of the possibilities of the bit currently under the read head.
Making a universal Turing machine is a very difficult exercise in encoding meanings. This has much more to do with mathematics than with programming. There are infinitely may solutions.
As far as I know, it could be that the situation could be similar as with Goedel numbers. Goedel proved that a number exists that represents a theorem that says "this theorem cannot be proven". Mathematician are not very interested in actually constructing such a number.
>Krishna
>[1] For those like me, who have not much CS >background, a Turing machine is the prototype >computing machine described by Alan Turing >in a 1936 paper. It is a simple state >machine with just a few instructions (less >than 10), but the Church-Turing assertion >states that it can be programmed to carry >out any algorithm, i.e. it's equivalent to >any digital computer that can be conceived. >Hope I got that right :)
The equivalence is a theorem, I always thought Turing proved that by himself. Church thesis is that any effective procedure can be somehow programmed into a computer. This is a philosophical stand that can hardly be proven.
Groetjes Albert -- Albert van der Horst,Oranjestr 8,3511 RA UTRECHT,THE NETHERLANDS Q.: Where is Bin? A.: With his ma. Q.: That makes the Saudi's terrorists, then? A.: No, George already owns their oil. alb...@spenarnc.xs4all.nl http://home.hccnet.nl/a.w.m.van.der.horst
>> ... The main operation for a turing machine emulator is >> however simple:
>> : <statex:0R|1L> ( p -- p' ) >> dup c@ IF 0 over c! 1+ <next0> ;THEN 1 over c! 1- <next1> ;
>> <next0> and <next1> jump to the next state labels, they don't need to >> return to their caller, that's why I use colorForth's ;THEN to express >> that.
> If p is the current tape position, then the above word > would read the bit at the current position, write the > inverse of the input bit at the current position, then > move left if the input was a 0 or move right if the input > was a 1. Is this operation general enough for a Turing > machine? I thought the movement direction and the write > bit (0, 1, or a blank) should be separate parts of the > instruction.
You have to replace the 0 and 1, the 1+ and 1- depending on what you do. This is the code for a machine with a 0R|1L "opcode" at that state.
> In article <3EBC7894.90BE7...@compuserve.com>, > Krishna Myneni <krishnamyn...@compuserve.com> wrote: > >Has anyone out there written a nice demo > >of a Turing machine[1] in Forth? It could > >probably be easily and elegantly done > >with JVN's finite state machine code, but > >maybe that's overkill. The demo should > >be capable of accepting a series of user > >entered program and showing the results > >after each cycle. Perhaps it's a standard > >exercise in an intro CS course to write > >such a virtual machine.
> This is a bit of a strange request. I think you confuse > Turing machines, and the concept of a universal Turing > machine.
Why is this a strange request? Since there is a possibile ambiguity about whether I mean Turing machine (TM) or Universal Turing Machine (UTM), let me be explicit about what I meant when I referred to a Turing Machine. The TM consists of the following:
1) A "program" which consists of a sequence of specifications of the form:
(q, x, w, q', m)
q <-> current state (qs, qh, 0, 1, 2, 3, ...)
x <-> input value from the virtual tape (0, 1, BLANK, TAPESTART)
w <-> output value to the virtual tape (0, 1, BLANK)
q' <-> next state (qs, qh, 0, 1, 2, ...)
m <-> movement for virtual tape (-1, +1)
The special states qs and qh are the starting and halting states.
2) An internal state value, q, representing the current state of the TM. Initially the TM starts in qs, the starting state.
3) A virtual tape device with sequential data written on the tape. At each sequential location, there may be one of four values: 0, 1, BLANK, TAPESTART. Of course TAPESTART is at the first location only. The rest of the data on the tape consists of the input to the TM.
4) The state-transition hardware which executes the program. Of course this is virtual hardware.
The TM operates as follows. When the TM is "turned on", the current state q is initialized to qs. The virtual tape is also positioned at the first location. Program execution consists of the following:
a) The TM searches the program until it finds an entry containing a q and x that match its current state and input value from the tape (which, initially, are q=qs and x=TAPESTART). If it fails to find a match, then it transitions to the state qh, the halting state.
b) If a matching instruction was found, it executes the instruction by writing w to the current tape position, moving the tape read/write head by the specified offset (-1 or +1), and setting the current state to q'.
c) if q' = qh, halt the TM else goto a)
It is non-obvious that such a machine can execute ANY algorithm (e.g. searching a database), which is what the Church-Turing thesis states. I wanted to see if anyone had already coded these specs in Forth to get a feel for what this sort of machine could do. Obviously since this would be a software simulation, the program instructions can be modified easily, so the TM doesn't have to be a single purpose computer. But, does allowing for the program instructions to change make it a UTM? If so, then it can be called a UTM.
> >[1] For those like me, who have not much CS > >background, a Turing machine is the prototype > >computing machine described by Alan Turing > >in a 1936 paper. It is a simple state > >machine with just a few instructions (less > >than 10), but the Church-Turing assertion > >states that it can be programmed to carry > >out any algorithm, i.e. it's equivalent to > >any digital computer that can be conceived. > >Hope I got that right :)
> The equivalence is a theorem, I always thought > Turing proved that by himself. > Church thesis is that any effective procedure > can be somehow programmed into a computer. > This is a philosophical stand that can hardly be proven.
Ok. I believe the equivalence of a TM with any digital computer is a mathematical theorem. The assertion that any algorithm can be programmed into a TM probably cannot be proven, but neither is it just a philosophical stand. It can potentially be disproven with a counter-example. In the nearly 70 years since the assertion was made, no one has provided an example of an algorithm that could not be encoded in a TM.
> > Why is this a strange request? Since there is a possibile ambiguity > about whether I mean Turing machine (TM) or Universal Turing Machine > (UTM), let me be explicit about what I meant when I referred to a > Turing Machine. The TM consists of the following: > > 1) A "program" which consists of a sequence of specifications of the > form: > > (q, x, w, q', m) > > q <-> current state (qs, qh, 0, 1, 2, 3, ...) > > x <-> input value from the virtual tape (0, 1, BLANK, TAPESTART) > > w <-> output value to the virtual tape (0, 1, BLANK) > > q' <-> next state (qs, qh, 0, 1, 2, ...) > > m <-> movement for virtual tape (-1, +1) > > The special states qs and qh are the starting and halting states. > > 2) An internal state value, q, representing the current state of the > TM. Initially the TM starts in qs, the starting state. > > 3) A virtual tape device with sequential data written on the tape. At > each sequential location, there may be one of four values: 0, 1, > BLANK, TAPESTART. Of course TAPESTART is at the first location only. > The rest of the data on the tape consists of the input to the TM. > > 4) The state-transition hardware which executes the program. Of > course this is virtual hardware. > > The TM operates as follows. When the TM is "turned on", the current > state q is initialized to qs. The virtual tape is also positioned at > the first location. Program execution consists of the following: > > a) The TM searches the program until it finds an entry containing a q > and x that match its current state and input value from the tape > (which, initially, are q=qs and x=TAPESTART). If it fails to find a > match, then it transitions to the state qh, the halting state. > > > b) If a matching instruction was found, it executes the instruction > by writing w to the current tape position, moving the tape read/write > head by the specified offset (-1 or +1), and setting the current > state to q'. > > c) if q' = qh, halt the TM else goto a) > > > It is non-obvious that such a machine can execute ANY algorithm (e.g. > searching a database), which is what the Church-Turing thesis states. > I wanted to see if anyone had already coded these specs in Forth to > get a feel for what this sort of machine could do. Obviously since > this would be a software simulation, the program instructions can be > modified easily, so the TM doesn't have to be a single purpose > computer. But, does allowing for the program instructions to change > make it a UTM? If so, then it can be called a UTM. >
You are right, above description is of a TM, not a UTM, and it cannot execute any program, unless it is specifically constructed to be universal. It helps to think of Turing Machines as of programs - one TM <=> one program. Each particular TM does one thing, whatever its state table (program) describes. A UTM is a specially constructed TM (program), that given the description of another TM (on its input tape), takes that description and emulates it. In this sense the UTM is equivalent to an OS - it can run any TM (program) it is given.
> Ok. I believe the equivalence of a TM with any digital computer is a > mathematical theorem. The assertion that any algorithm can be > programmed into a TM probably cannot be proven, but neither is it > just a philosophical stand. It can potentially be disproven with a > counter-example. In the nearly 70 years since the assertion was made, > no one has provided an example of an algorithm that could not be > encoded in a TM. > You are right, what is proven is the equivalence of a UTM and a stored-memory computer. That a TM/computer can implement any algorithm, is (still) a conjecture.
-- I want to be a nothing-knower, Elko Tchernev a little ant on any hill; etch...@cs.umbc.edu for time is dead, the sun is over www.gl.umbc.edu/~etcher1 and there is nothing left to kill.
