INTERCAL Turing-completeness proof

== Interpreter for P′′ in INTERCAL-72 ==
Links: INTERCAL, P′′, F2, Brainfuck and Boolfuck
* Note that this interpreter implements both left- and right-infinite P′′... If you say that .3 is data-right, .4 is data-left, < moves the pointer right and that +> toggles and moves left (extending if need be), then you end up with the original (left-infinite) P′′. 
 
 DO (22) NEXT
___________________________________________________________
INTRODUCTION
 This is a P interpreter written in INTERCAL-72. 
 This proves that INTERCAL-72 is Turing complete. The 
 interpreter isn't very well written, and I haven't 
 deliberately tried to obfuscate the code (other than 
 writing it in INTERCAL, which is enough on it's own). It 
 is also very, very, very, very, painfully, excruciatingly 
 slow. It is probably bug-ridden (I haven't tested it), 
 but the principle should be sound. I know that there 
 aren't enough PLEASE's in it.
 
 It can't interpret P directly, but there is a 
 mechanical translation from P to a form this 
 interpreter understands.
 
 Note:
 'interpreter' means the program written in INTERCAL, 
 'program' means the program written in P.
 
 If you find any bugs or simplifications, just alter the 
 interpreter's source text.
LANGUAGE IMPLEMENTED
 P with a right-infinite tape (instead of left-
 infinite), and a two element alphabet (0 and 1). However, 
 I will use the Brainfuck/F2 symbols instead of the 
 original P symbols.
 
 [ if bit in current location is 0, jump past matching 
 ] and continue executing. Otherwise a no-op (go to 
 next instruction).
 ] jump back to matching [ and begin executing it.
 < move 'data pointer' left one bit (if this reaches 
 the start of the tape, the interpreter stops).
 +> toggle bit in current location, move tape pointer 
 right one bit (note that the tape extends 
 infinitely to the right).
 end if reached, the interpreter stops.
MESSAGES
 
 (CLC-INTERCAL messages.)
 
 *621 Pointless RESUME
 The interpreter tried to execute a #0 (i.e. finished).
 
 *632 Program terminated via RESUME
 The interpreter tried to execute an invalid (too large a 
 value) instruction. The maximum is #4.
 
 *436 Register .1 stashed away too well
 The interpreter reached a #2 ']', started scanning 
 backwards to find the corresponding #1 '[', but fell off 
 the beginning.
 
 *436 Register .2 stashed away too well
 The interpreter reached a #1 '[', started scanning 
 forwards to find the corresponding #2 ']', but fell off 
 the end.
 
 *436 Register .3 stashed away too well
 The interpreter reached a #3 '<', but was at the 
 beginning of the tape (it only extends to the right).
 
 Any other error messages (and unknown causes of the above 
 errors) are probably bugs in the interpreter. 
IMPLEMENTATION STATS *
 Note: ignoring comments.
 Used:
 Calculate and expressions (' " ¢ ¥ V ~).
 STASH and RETRIEVE.
 NEXT, RESUME and FORGET.
 Only 5 one-spot variables (.1 to .5).
 Only 5 constants (#0 to #4).
 Only 21 line labels.
 Only 4 levels on the NEXT stack.
 
 Not used:
 NOT, N'T, ABSTAIN FROM and REINSTATE.
 IGNORE and REMEMBER.
 32-bit registers and arrays.
 % ! + & , : and ; 
 GIVE UP.
 I/O.
 Invalid statements as error messages.
 The subroutine library.
 $ and ? (as substitutes for ¢ and ¥)
 COME FROM.
 
 [and, for completeness w.r.t. CLC-INTERCAL:
 computed %, computed labels, object-orientation, 
 BELONGS, ENSLAVE, FREE, NEXT FROM, indirection, 
 overloading, internal stuff, *, @, ?, $, _, ^, |, \, 
 /, assigning to constants, CONVERT, SWAP, CREATE, 
 DESTROY, iasm, WHILE, Quantum INTERCAL, INTERNET and 
 system calls.]
 
 * sorry, statisticians out there; these are technically 
 facts. (A statistic is a function of a random sample.)
THE DSTACK DATA STRUCTURE
 The main data structure used in the interpreter is (for 
 lack of a better name) called a 'dstack'. A dstack stores 
 an extensible tape, with a 'pointer' or 'current node'. 
 
 It is implemented with a pair of registers, which store 
 the left part and the right part of the dstack, as two 
 STASH-stacks:
 
 left right
 ------------------
 2 (not used) <- the value currently in the regs.
 ------------------
 7 2 \
 0 14586 the STASHed values in the regs.
 0 / 
 
 This represents the list/tape:
 --- 
 ( 0 7 | 2 | 2 14586 0 )
 --- 
 current node
 
 The current node is the current value in the left 
 register. The right register's current value is garbage, 
 except when 'moving the pointer' with code like:
 
 Moving pointer right:
 
 DO right <- left
 DO STASH right
 DO RETRIEVE left
 
 Moving pointer left:
 
 DO STASH left
 DO RETRIEVE right
 DO left <- right
 
 Note that some kind of end-of-list marker (a so-called 
 'sentinel') is useful at each end of the dstack (the 0's
 in this example).
 
 (Remember, INTERCAL provides no simple way to check if 
 there is anything to RETRIEVE.) 
 
 Sentinels are not absolutely necessary - in this 
 interpreter they are not used everywhere - but you have 
 to make sure you won't overshoot the ends some other way.
 
THE COUNTER
 
 The 'loop depth' register (see below) is stored as a 
 counter.
 
 A counter stores an unbounded natural number, i.e. a 
 number in the set {0, 1, 2, ...}. You can: zero it, 
 increment it, decrement it and test it.
 
 Note: decrementing 0 results in undefined behaviour!
 
 It is implemented as a single STASH-stack in a register:
 
 zero
 DO reg <- #1
 
 increment
 DO STASH reg
 DO reg <- #2
 
 decrement
 DO RETRIEVE reg
 
 test ...
 DO (x) NEXT
 ... case: counter is not zero
 DO (end) NEXT
 (x) DO (y) NEXT
 PLEASE FORGET #1
 ... case: counter is zero
 DO (end) NEXT
 (y) DO RESUME reg
 (end)
 ...
 
NOTES ON THE IMPLEMENTATION
 Both the P program and its data are stored as dstacks. 
 The data store ends with a #2 sentinel - when attempting 
 to move onto this cell, the interpreter inserts a #0 cell 
 transparently.
 
 To match brackets when a loop condition fails, the 
 interpreter scans through the code using a 'loop depth' 
 register. This is a counter that stores the depth to 
 which loops have been nested. It starts at 0, is 
 incremented when entering a loop, and is decremented and 
 tested when leaving a loop. The test decides whether to 
 continue scanning or to stop.
 
REGISTERS
 
 .1 code left
 .2 code right
 .3 data left
 .4 data right
 .5 loop depth
 
USAGE
 The P program goes below, between lines 22 and 1, 
 entered backwards. It is encoded as follows:
 
 end #0
 [ #1
 ] #2
 < #3
 +> #4
 
 NOTE: a #0 inside a loop whose condition has failed will 
 be ignored, like #3 and #4, so you can use it to 
 conditionally GIVE UP (unlike a previous version).
 
 Replace the [bracketed text] below with the constants.
___________________________________________________________
(22) DO FORGET #1
 
 
 DO .2 <- [last]
 DO STASH .2
 DO .2 <- [2nd last]
 DO STASH .2
 ...
 DO .2 <- [2nd]
 DO STASH .2
 DO .2 <- [1st]
 DO STASH .2
 
 
 DO .3 <- #2
 DO STASH .3
 DO .3 <- #0
 DO .4 <- #2
 DO STASH .4
 
 DO (1) NEXT
(1) PLEASE FORGET #1
 
 DO STASH .1
 DO RETRIEVE .2
 DO .1 <- .2
 
 DO (4) NEXT
 DO .3 <- '¥.3¢#1'~#1
 DO STASH .3
 DO RETRIEVE .4
 DO .3 <- .4
 DO (2) NEXT
 DO .3 <- #0
 DO STASH .4
 DO (1) NEXT
(2) DO (3) NEXT
 PLEASE FORGET #1
 DO (1) NEXT
(3) DO RESUME '¥".3~#2"¢#1'~#3
 
(4) DO (5) NEXT
 PLEASE FORGET #1
 DO .4 <- .3
 DO STASH .4
 DO RETRIEVE .3
 DO (1) NEXT
 
(5) DO (12) NEXT
 PLEASE FORGET #2
 DO .5 <- #1
 DO (6) NEXT
(6) PLEASE FORGET #1
 DO .2 <- .1
 DO STASH .2
 DO RETRIEVE .1
 DO (7) NEXT
 DO (6) NEXT
(7) DO (8) NEXT
 PLEASE FORGET #1
 DO STASH .5
 DO .5 <- #2
 DO (6) NEXT
(8) DO (11) NEXT
 PLEASE FORGET #2
 DO (9) NEXT
 DO RETRIEVE .5
 DO (6) NEXT
(9) DO (10) NEXT
 PLEASE FORGET #1
 DO .2 <- .1
 DO STASH .2
 DO RETRIEVE .1
 DO (1) NEXT
(10) DO RESUME .5
(11) DO RESUME 'V ".1~#3" ¢ "V'"¥'.V1~#1'¢#1"~#1'¢#0"'
 
(12) DO (21) NEXT
 PLEASE FORGET #3
 DO (13) NEXT
 DO (1) NEXT
(13) DO (14) NEXT
 PLEASE FORGET #1
 DO .5 <- #1
 DO (15) NEXT
(14) DO RESUME '¥"'.3~.3'~#1"¢#1'~#3
(15) PLEASE FORGET #1
 DO STASH .1
 DO RETRIEVE .2
 DO .1 <- .2
 DO (16) NEXT
 DO (15) NEXT
(16) DO (19) NEXT
 PLEASE FORGET #1
 DO (17) NEXT
 DO RETRIEVE .5
 DO (15) NEXT
(17) DO (18) NEXT
 PLEASE FORGET #1
 DO (1) NEXT
(18) DO RESUME .5
(19) DO (20) NEXT
 PLEASE FORGET #2
 DO STASH .5
 DO .5 <- #2
 DO (15) NEXT
(20) DO RESUME 'V ".1~#3" ¢ "V'"¥'.V1~#1'¢#1"~#1'¢#0"'
 
(21) DO RESUME .1
Category:Proofs