INTERCAL Turing-completeness proof

From Esolang
Jump to: navigation, 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 .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