rockwell@socrates.umd.edu (Raul Rockwell) (06/12/91)
A Turing machine emulator is not the most practical sort of program one could write, but in case anyone is interested, here's one I threw together recently. First, how to extract the program from this article: use )sscript file where "file" is the name of a file which contains this article. J will reject all the invalid lines, but will execute every line which is a valid J sentence. One of the tricks you can pull with J is reading from standard input in a script, so my bootstrap loader looks like this: read =. 1!:1 readblock =. (read 1 1 1 1) : '' r=. 0 0 $ '' loop) r=. r, l=. read 1 $.=. end [~:(0=#l) loop end) r "readblock" is a verb which will read standard input up through the first blank line and return the result as a character matrix. Part of the purpose of this article is to point out how easy it is to distribute J programs in news articles, so feel free to use this technique... Second item, just what *is* a Turing machine? Let's see, a Turing machine has a read/write head which is positioned over a tape. At discrete units of time, it will either: (a) change the symbol under the read/write head (b) move to the next square on the left (c) move to the next square on the right (d) stop Which action it chooses depends on the symbol currently under the tape head, and the internal state of the machine. So Turing microcode is generally expressed as a four element list: 0 initial state of machine 1 initial symbol under the tape head 2 what action the machine takes 3 final state of the machine. Being somewhat lazy, I decided to use numbers to represent Turing machine symbols. I reserved negative numbers to represent tape head movement, _1 meaning move left, and _2 meaning move right. The initial internal state of the machine is 0, and if the read head goes off the end of the tape, the tape is padded with zeros. The machine halts when it reaches an internal-state/tape-symbol combination for which it has no microcode. So here are a few sample microcode instructions for a Turing machine: MoveRightIf1 =. 3 1 _2 3 This will scan right until the machine finds a non-1 cell. MoveLeftIf1=. 4 1 _1 4 This will scan left until the machine finds a non-1 cell. To connect them, I'll use Set1=. 3 0 1 4 In other words, if the machine finds a zero, it will change it to a one, and switch to internal state 4. Finally, to start, I'll assume I'm over a zero, and that the tape I want to play with is immediately to the right: StartThis=. 0 0 _2 3 Now, my machine description will consist of a two element boxed array. The first element is the microcode (in matrix form), and the second element is the initial tape. Something like this: [] sample =. (>3 1 _2 3; 4 1 _1 4; 3 0 1 4; 0 0 _2 3) ; 0 1 1 1 +--------+-------+ |3 1 _2 3|0 1 1 1| |4 1 _1 4| | |3 0 1 4| | |0 0 _2 3| | +--------+-------+ After the machine runs, I'd expect that the tape would look like this: 0 1 1 1 1 (That assumes I don't make any typos coping my printout). I think that should be enough documentation, here's the program: usage =. readblock '' print =. 1!:2&2 print 'Usage:' print ' mode TM quads;tape' print ' ------------------' print ' mode is: ''quiet''' print ' or ''trace''' print ' or ''step''' print ' quads is the program' print ' tape is the data' TM=. usage : (_1 1 }. readbloc '') X X X 'proverbial system calls' Xread =. 1!:1 Xprint=. 1!:2 & 2 X X 'determine noise level' Xmode=. 1 i.~('quiet';'trace';'step')e. ;: x. Xcontinue=. >(loop;trace;step;abort) {~ mode X X 'unpack machine and tape description' X('prefixes';'cursor') =. y. X Xsuffixes =. 2 3 {"1 prefixes Xprefixes =. 0 1 {"1 prefixes X Xright_tape =. 1 }. cursor Xcursor =. 1 {. cursor Xleft_tape =. i. 0 X Xstate =. 0 Xend =. #prefixes X X 'begin execution' X$.=. continue Xabort) $:$.=.'' X Xstep) print left_tape;state;cursor,right_tape X ". read 1 X $. =. loop X Xtrace) print left_tape;state;cursor,right_tape X Xloop) next =. prefixes i. state, cursor X $.=. halt [^:(next=end) eval Xeval) ('action';'state')=. next{suffixes X $.=. move [^:(action<0) set Xset) cursor =. action X $.=. continue X Xmove) $.=. goleft [^:(action=_1) goright Xgoright) left_tape =. left_tape,cursor X cursor=. 1{. right_tape X right_tape =. 1}. right_tape X $.=. continue X Xgoleft) right_tape =. cursor,right_tape X cursor =. _1{. left_tape X left_tape =. _1}. left_tape X $.=.continue X Xhalt) left_tape;state;cursor,right_tape One final comment, the descriptions of the machine, while it is running and afterwords are three element boxed lists. The first element is the tape to the left of the read/write head. The second element is the internal state of the machine. The third element is the tape cell under the head, and the tape to the right of that. So, if you executed 'quiet' TM sample, you should get a result like: ++-+---------+ ||4|0 1 1 1 1| ++-+---------+ Hopefully, I've not made any mistakes typing this in... -- Raul <rockwell@socrates.umd.edu>
rockwell@socrates.umd.edu (Raul Rockwell) (06/16/91)
I wrote: One of the tricks you can pull with J is reading from standard input in a script, so my bootstrap loader looks like this: read =. 1!:1 readblock =. (read 1 1 1 1) : '' r=. 0 0 $ '' loop) r=. r, l=. read 1 $.=. end [~:(0=#l) loop end) r AARRRRGGGGHHHHH!!!!!!!! the second line from the bottom should read: $.=. end [^:(0=#l) loop [Mr. Hui, please, please, please, could you port J to HP/PA? I wouldn't have this sort of problem if I had a working version of J on this system. [Incidentally, anyone in Toronto have telnet access that they could let Mr. Hui use to do the port???]] Finally, I've re-written the TM emulator in a more concise and [I think] clearer fashion, maybe once I'm sure I've got a copy of it that is totally debugged I'll re-post. *sigh* -- Raul <rockwell@socrates.umd.edu>