INTERCAL Turing-completeness proof
Jump to navigation
Jump to search
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
.3is data-right,.4is 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