Turing machine demo?
Krishna Myneni
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 :)
Marcel Hendrix
> 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
TURMITE, RedPole
\ <state> <colour> <angle>
( in=0) 0 C, white C, 1 C,
( in=1) 0 C, black C, 3 C,
TURMITE, Spiral
\ <state> <colour> <angle>
( in=0) 0 C, white C, 1 C,
( in=1) 1 C, black C, 0 C,
( in=0) 0 C, red C, 3 C,
( in=1) 0 C, red C, 3 C,
DEFER turmite PRIVATE
: DoRedPole ['] RedPole IS turmite ;
: DoSpiral ['] Spiral IS turmite ;
TRUE VALUE ?border
#40 VALUE dimension PRIVATE
0 VALUE zz PRIVATE
: gbox zz zz Xmax zz 2* - Ymax zz 2* -
GETCOLOR RECTANGLE ; 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 ;
:ABOUT CR ." enter ( doRedPole | doSpiral ) DO-IT " ;
DoRedPole
.ABOUT -turmites CR
DEPRIVE
(* End of Source *)
Peter Lawrence
>
> 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.
--
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.
See http://users.netlink.com.au/~peterl/publicns.html#AFRLET2 and the other
items on that page for some reasons why.
Alex Vinokur
"Krishna Myneni" <krishn...@compuserve.com> wrote in message news:3EBC7894...@compuserve.com...
> Has anyone out there written a nice demo
> of a Turing machine[1] in Forth?
Not Forth, but C++ :
Turing Machine (C++ Simulator)
http://alexvn.freeservers.com/s1/turing.html
http://sourceforge.net/projects/turing-machine
==========================================
Alex Vinokur
mailto:ale...@connect.to
http://www.simtel.net/pub/oth/19088.html
http://sourceforge.net/users/alexvn
==========================================
Joel Rubin
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.
Krishna Myneni
>
> 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):
Looks very close. Thanks.
Krishna
Krishna Myneni
>
> Krishna Myneni wrote:
> >
> > 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?
Krishna
John Fraser
> 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.
> Krishna
Cheers,
John
John Fraser
news:5qmpbv8sqgrq935de...@4ax.com...
> 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".
That's great! ROTFL.
John Fraser
> 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.
Cheers,
John
Peter Lawrence
>
> Peter Lawrence wrote:
> >
> > Krishna Myneni wrote:
> > >
> > > 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
.
.
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.
Bernd Paysan
> 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.
--
Bernd Paysan
"If you want it done right, you have to do it yourself"
http://www.jwdt.com/~paysan/
Krishna Myneni
>
> ... The main operation for a turing machine emulator is
>
> : <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.
Krishna
Albert van der Horst
Krishna Myneni <krishn...@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
Bernd Paysan
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.
Krishna Myneni
>
> In article <3EBC7894...@compuserve.com>,
> Krishna Myneni <krishn...@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.
> ....
> >
> >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.
>
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.
Cheers,
Krishna
Elko Tchernev
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; etc...@cs.umbc.edu
for time is dead, the sun is over www.gl.umbc.edu/~etcher1
and there is nothing left to kill.