SuperPro Turing Machine

Post details of your projects here.
Post Reply
jwillis172
Posts: 3
Joined: Wed Nov 12, 2014 8:20 pm

SuperPro Turing Machine

Post by jwillis172 »

I’ve always been fascinated with the history of computers. Who invented the first one? What was their first design? Why did people want a computer? When were computers first invented? I am going to attempt to tie the current generation of microcontrollers, such as the NXP LPC1756, back to the first theoretical concept of the computer.

On November 12, 1936, Alan M. Turing published a paper https://www.cs.virginia.edu/~robins/Tur ... _1936.pdf in which he described a theoretical computing machine as follows:

The machine is supplied with a "tape" (the analog of paper) running through it and divided into sections (called "squares"),
each capable of bearing a "symbol." At anyone moment there is only one square, say the rth, bearing the symbol G(r) which
is "in the machine." We may call this square the "scanned square." The "scanned symbol" is the only one of which the
machine is, so to speak, "directly aware." However, by altering its m-configuration, the machine can effectively remember
some of the symbols which it has "seen" (scanned) previously. The possible behavior of the machine at any moment is
determined by the m-configuration g(n) and the scanned symbol G(r). This pair g(n), G(r) will be called the "configuration."

Thus, the configuration determines the possible behavior of the machine. In some configurations in which the scanned
square is blank (ie: bears no symbol) the machine writes down a new symbol on the square; in other configurations, it erases
the scanned symbol. The machine may also change the square, which is being scanned, but only by shifting it one space to
right or left.

I suppose there is some room for interpretation here. Turing has described a computer with a separate program and data memory space. The “program” and program counter comprise the program memory space and the “tape” and tape index comprise the data memory space. Turing and John Von Neumann https://web.archive.org/web/200704210 ... umann.html would apply this concept in 1944 to the design of the ENIAC computer. The rest is history.

I was fascinated with Turing’s concept especially since this is the simplest computer possible and that it is capable of computing anything that is “computable” https://en.wikipedia.org/wiki/Church%E2 ... ing_thesis. I built prototype Turing machines in hardware using TTL logic, in assembly language and in FORTRAN, as published in BYTE Magazine April 1981https://archive.org/details/byte-magazine-1981-04 .

There was one caveat, Turing’s machine has an infinite amount of memory. A practical Turing machine has a finite amount of memory.

I now present a working practical Turing machine implemented using a Coridium SuperPro.
Turing machine architecture.png
Turing machine architecture.png (144.65 KiB) Viewed 3537 times
Figure 1 – Turing machine architecture comprising a stored program, program counter, a tape, tape index and register.
How Does the Turing machine work?

Google supplied us with an example of a Turing machine counting in binary. Their example makes use of the definition that a square of the tape can be blank. The “doodle” can be found here .
Turing machine doodle.png
Turing machine doodle.png (39.03 KiB) Viewed 3537 times
Figure 2- Google Turing Machine Doodle - counting in binary.

Cool! But what are we going to do with the SuperPro? Let’s start with the Google Turing Machine Doodle.

Analysis of the “Count up in binary” Program

If you haven’t already done so, go back and watch the Google Turing Machine Doodlehttps://www.google.com/doodles/alan-tur ... h-birthday. Their first example counts-up in binary. Starting with a blank tape, the logic goes like this:

Program statement 4: Is it a zero? Write zero, move left and go to 4. Is it a one? Write one, move left and go to 4. Is it blank? Write a blank, move right and go to 5. This is abbreviated:

{4, '0', 'L', 4, '1', 'L', 4, '_', 'R', 5}, // move left until blank

Program statement 5: Is it a zero? Write one, “stay” and go to 4. Is it a one? Write a zero, move right and go to 5. Is it blank? Write a one, “stay” and go to 4. This is abbreviated:

{5, '1', 'S', 4, '0', 'R', 5, '1', 'S', 4} // move right and count

Let’s work through the Google Turing Doodle example. Starting with a blank tape and from program counter 4:

[_][_][_][_][_][_][_][_], REGISTER is “_”, write a “_”, move right and go to 5.
^ tapeIndex
[_][1][_][_][_][_][_][_], REGISTER is “_”, write a “1”, stay and go to 4.
^ tapeIndex
[_][1][_][_][_][_][_][_], REGISTER is “1”, write a “1”, move left and go to 4.
^ tapeIndex
[_][1][_][_][_][_][_][_], REGISTER is “_”, write a “_”, move right and go to 5.
^ tapeIndex
[_][1][_][_][_][_][_][_], REGISTER is “1”, write a “0”, move right and go to 5.
^ tapeIndex
[_][0][1][_][_][_][_][_], REGISTER is “_”, write a “1”, stay and go to 4.
^ tapeIndex
[_][0][1][_][_][_][_][_], REGISTER is “1”, write a “1”, move left and go to 4.
^ tapeIndex
[_][0][1][_][_][_][_][_], REGISTER is “0”, write a “0”, move left and go to 4.
^ tapeIndex
[_][0][1][_][_][_][_][_], REGISTER is “_”, write a “_”, move right and go to 5.
^ tapeIndex
[_][0][1][_][_][_][_][_], REGISTER is “0”, write a “1”, move right and go to 4.
^ tapeIndex
[_][1][1][_][_][_][_][_], REGISTER is “1”, write a “1”, move left and go to 4.
^ tapeIndex
[_][1][1][_][_][_][_][_], REGISTER is “_”, write a “_”, move right and go to 5.
^ tapeIndex
[_][1][1][_][_][_][_][_], REGISTER is “1”, write a “0”, move right and go to 5.
^ tapeIndex
[_][0][1][_][_][_][_][_], REGISTER is “1”, write a “0”, move right and go to 5.
^ tapeIndex
[_][0][0][_][_][_][_][_], REGISTER is “1”, write a “0”, move right and go to 5.
^ tapeIndex
[_][0][0][_][_][_][_][_], REGISTER is “_”, write a “1”, stay and go to 4.
^ tapeIndex
[_][0][0][1][_][_][_][_], REGISTER is “_”, write a “1”, stay and go to 4.
^ tapeIndex
The tape ends up looking like this:
___
_1_
_01_
_11_
_001_
And so on.

Presto, we’re counting in binary.

The key question for Turing machines is: “Will a given program and tape halt or keep going forever?”

A related question is: “How long will it take for a given program and tape to perform the computing task?” This question can be rephrased for our example as: “How long will it take to count to N?” To answer this question for our binary counting example I made the following graph:
computations vs N.png
computations vs N.png (45 KiB) Viewed 3452 times
Figure 3- Turing program computations required to reach a number using the binary counting program.
As you can see the number of computations required is linear with the number reached.

Design Enhancements

A couple of features were added to the basic SuperPro Turing machine to allow RUN/STOP control and manual UP/DOWN manipulation of the program counter. Two switches were added, a SPST for RUN/STOP and a momentary contact SPDT for UP/DOWN. When the RUN/STOP switch is in the RUN position, the Turing machines runs normally. When the RUN/STOP switch is in the STOP position, the Turing machine is stopped, and the program counter switches are active. With this feature you can put the RUN/STOP in the STOP position, then reset the SuperPro. The tape index and program counter are initialized to zero and the tape is initialized to blanks. From there, use the UP/DOWN switch to set the program counter to the desired Turing program and flip to RUN.

So how do you know when the program has halted? One technique is to go to a particular program line, such as the last available program statement and use something like:

{63, '0', 'S', 63, '1', 'S', 63, '_', 'S', 63} // HALT with program counter set to ‘111111.

Conclusion

I hope you’ve enjoyed this journey into the origins of computing. In my opinion, the most powerful concept in the Turing paper is the concept of state, which he called “configuration”. To paraphrase Turing:

This pair, tape[tapeIndex] and program[programCounter] will be called the "state."

Today we might implement a state machine as follows:

switch(state)
{
case 1:
do something;
case 2:
do something else;
default:
do nothing;
}

In this example, “state” controls the program counter indirectly through the “switch” construct.

I asserted that a Turing machine is capable of computing anything that is “computable”. This is similar to the assertion; all logic can be built using NAND gates. This assertion is relatively easy to prove by giving examples of other logic, such NOT, AND, OR, XOR, JK flip flops and RS flip flops cells can be built from NAND gates.

I suppose my next project will be to build a Turing machine using only NAND gates!

Code: Select all

/********************************************************************************************/
/*                                                                                                             */
/*                                          turingMachine.c                                           */
/*  Jim Willis                                                                                             */
/*  Jan. 31, 2022                                                                                       */
/*                                                                                                             */
/*******************************************************************************************/

#include "coridium_pcb.h"       // this one is required for the proper CPU configures
#include "printf.h"
#include "uart.h"
#include "breakpoint.h"         // this one is required to suppress "IgnoreFault" error message

#define LED_PIN                 74

#define ZEROTOKEN               '0'
#define ONETOKEN                '1'
#define BLANKTOKEN              '_'

// output pins
#define OUTPUT_REGISTER             29  // output pin for register
#define OUTPUT_WRITE                30  // output pin for write
    
#define PROGRAM_COUNTER_BIT0        50  // PROGRAM COUNTER
#define PROGRAM_COUNTER_BIT1        52  //
#define PROGRAM_COUNTER_BIT2        55  //
#define PROGRAM_COUNTER_BIT3        57  //
#define PROGRAM_COUNTER_BIT4        60  //
#define PROGRAM_COUNTER_BIT5        0   // PROGRAM COUNTER

#define TAPE_INDEX_BIT0             15  // 72, 73 are reserved for TXD2 and RXD2        10
#define TAPE_INDEX_BIT1             16  //                                              11
#define TAPE_INDEX_BIT2             17  //                                              1
#define TAPE_INDEX_BIT3             22  //        In case you reverse your wiring ->    61
#define TAPE_INDEX_BIT4             51  //        like I did                            58
#define TAPE_INDEX_BIT5             54  //                                              56
#define TAPE_INDEX_BIT6             56  //                                              54
#define TAPE_INDEX_BIT7             58  //                                              51
#define TAPE_INDEX_BIT8             61  //                                              22
#define TAPE_INDEX_BIT9             1   //                                              17
#define TAPE_INDEX_BIT10            11  //                                              16
#define TAPE_INDEX_BIT11            10  //                                              15

#define PC_DN_PIN               67
#define PC_UP_PIN               68
#define RUN_STOP_PIN            69

#define DEBOUNCE_TIME   100
#define REPEAT_TIME     1000

/********************************************************************************************/
/*                                                                                                              */
/* void                                                                                                      */
/* setProgramCounterPins(int programCounter)                                          */
/*                                                                                                             */

void
setProgramCounterPins(int programCounter)
{
    ((programCounter & 0x0001)!=0)? HIGH (PROGRAM_COUNTER_BIT0) : LOW (PROGRAM_COUNTER_BIT0);
    ((programCounter & 0x0002)!=0)? HIGH (PROGRAM_COUNTER_BIT1) : LOW (PROGRAM_COUNTER_BIT1);
    ((programCounter & 0x0004)!=0)? HIGH (PROGRAM_COUNTER_BIT2) : LOW (PROGRAM_COUNTER_BIT2);
    ((programCounter & 0x0008)!=0)? HIGH (PROGRAM_COUNTER_BIT3) : LOW (PROGRAM_COUNTER_BIT3);
    ((programCounter & 0x0010)!=0)? HIGH (PROGRAM_COUNTER_BIT4) : LOW (PROGRAM_COUNTER_BIT4);
    ((programCounter & 0x0020)!=0)? HIGH (PROGRAM_COUNTER_BIT5) : LOW (PROGRAM_COUNTER_BIT5);
    
}                        
/*                                                                                                              */
/********************************************************************************************/
/********************************************************************************************/
/*                                                                                                              */
/* void                                                                                                       */
/* setTapeIndexPins(int tapeIndex)                                                             */
/*                                                                                                              */

void
setTapeIndexPins(int tapeIndex)
{
    
    ((tapeIndex & 0x0001)!=0)? HIGH (TAPE_INDEX_BIT0)  : LOW (TAPE_INDEX_BIT0);  
    ((tapeIndex & 0x0002)!=0)? HIGH (TAPE_INDEX_BIT1)  : LOW (TAPE_INDEX_BIT1);  
    ((tapeIndex & 0x0004)!=0)? HIGH (TAPE_INDEX_BIT2)  : LOW (TAPE_INDEX_BIT2);  
    ((tapeIndex & 0x0008)!=0)? HIGH (TAPE_INDEX_BIT3)  : LOW (TAPE_INDEX_BIT3);  
    ((tapeIndex & 0x0010)!=0)? HIGH (TAPE_INDEX_BIT4)  : LOW (TAPE_INDEX_BIT4);  
    ((tapeIndex & 0x0020)!=0)? HIGH (TAPE_INDEX_BIT5)  : LOW (TAPE_INDEX_BIT5);  
    ((tapeIndex & 0x0040)!=0)? HIGH (TAPE_INDEX_BIT6)  : LOW (TAPE_INDEX_BIT6);  
    ((tapeIndex & 0x0080)!=0)? HIGH (TAPE_INDEX_BIT7)  : LOW (TAPE_INDEX_BIT7);  
    ((tapeIndex & 0x0100)!=0)? HIGH (TAPE_INDEX_BIT8)  : LOW (TAPE_INDEX_BIT8);  
    ((tapeIndex & 0x0200)!=0)? HIGH (TAPE_INDEX_BIT9)  : LOW (TAPE_INDEX_BIT9);  
    ((tapeIndex & 0x0400)!=0)? HIGH (TAPE_INDEX_BIT10) : LOW (TAPE_INDEX_BIT10);    
    ((tapeIndex & 0x0800)!=0)? HIGH (TAPE_INDEX_BIT11) : LOW (TAPE_INDEX_BIT11); 
}
/*                                                                                                              */
/********************************************************************************************/

#include ".\tape.h"
#include ".\program.h"

int tapeIndex = 0;

int programCounter = 0;

/********************************************************************************************/
/*                                                                                                             */
/* void                                                                                                      */
/* main()                                                                                                  */
/*                                                                                                            */

void
main()
{
    int j, writeToken, repeatTime;

    SystemInit();                   // initializes clocks
    UART_init(0,115200);            // turns on UART0 
    systick_init();                 // sets up SysTick as the TIMER 1usec tick

    OUTPUT(LED_PIN);
    OUTPUT(OUTPUT_WRITE);
    OUTPUT(OUTPUT_REGISTER);
    OUTPUT(PROGRAM_COUNTER_BIT0);
    OUTPUT(PROGRAM_COUNTER_BIT1);
    OUTPUT(PROGRAM_COUNTER_BIT2);
    OUTPUT(PROGRAM_COUNTER_BIT3);
    OUTPUT(PROGRAM_COUNTER_BIT4);
    OUTPUT(PROGRAM_COUNTER_BIT5);
    INPUT (RUN_STOP_PIN);
    
    
    // INPUT (RUN_STOP_PIN);
    printf("Program name: %s\r", programName);
    puts("|------------------------------|\r"); 
    puts("|           Turing machine     |\r");
    puts("|              PROGRAM         |\r");
    puts("|------------------------------|\r");
    puts("|   | -if 0--| -if 1--| -if 1--|\r");
    puts("|  #| W D ADR| W D ADR| W D ADR|\r");
    puts("|------------------------------|\r");
    for (j=0 ; j<PROGRAMLINES ; ++j)
    {
        if (program[j].writeIfZero == '\0') break;

        printf("|%3d| %c %c %3d| %c %c %3d| %c %c %3d|\r", program[j].lineNumber,
                                            program[j].writeIfZero, 
                                            program[j].directionIfZero,
                                            program[j].go toIfZero,
                                            program[j].writeIfOne,
                                            program[j].directionIfOne,
                                            program[j].go toIfOne,
                                            program[j].writeIfBlank,
                                            program[j].directionIfBlank,
                                            program[j].go toIfBlank);
    }
    // initialize tape to blanks 
    for (j=0 ; j<TAPEBYTES ; ++j)
    {
        writeTape(tape, j, BLANKTOKEN);
    }

    while(1)
    {
    
        if (IN(RUN_STOP_PIN)== 0)                       // read the RUN_STOP_PIN
        {
            writeToken = process(tape, program);
            
            if (writeToken==ONETOKEN)
            {   
                LOW(LED_PIN);
                HIGH (OUTPUT_REGISTER);
            }
            else if (writeToken==ZEROTOKEN)
            {
                HIGH(LED_PIN);
                LOW (OUTPUT_REGISTER);
            }
            else if (writeToken==BLANKTOKEN)
            {
                // do nothing
            }
            setProgramCounterPins(programCounter);
            setTapeIndexPins(tapeIndex);
            
            // slow down execution for parity program
            if (programCounter == 1 || programCounter == 2)
            {
                // wait 80 microseconds to keep audio below 12.5 kHz
                WAITmicro(80);
            }

        }
        else // do this in STOP mode
        {
            repeatTime = REPEAT_TIME;
            
            if (IN (PC_UP_PIN)==0)
            {
                WAIT (DEBOUNCE_TIME);                       // debounce

                while (IN (PC_UP_PIN)==0)
                {   
                    ++programCounter;
                    if (programCounter>=PROGRAMLINES)       // wrap around
                    {
                        programCounter = 0;                 // wrap around
                    }
                    printf("programCounter= %d\n", programCounter);
                    WAIT (repeatTime);                      // auto repeat
                    if (repeatTime>200) repeatTime -= 200;
                }
            }
            else if (IN (PC_DN_PIN)==0)
            {
                WAIT (DEBOUNCE_TIME);                       // debounce

                while (IN (PC_DN_PIN)==0)
                {
                    --programCounter;
                    if (programCounter<0)                   // wrap around
                    {
                        programCounter = PROGRAMLINES-1;
                    }
                    printf("programCounter= %d\n", programCounter);
                    WAIT (repeatTime);                      // auto repeat
                    if (repeatTime>200) repeatTime -= 200;
                }
            }
        }
    }
}

/*                                                                                                              */
/********************************************************************************************/

/********************************************************************************************/
/*                                                                                                             */
/*                                      end turingMachine.c                                         */
/*                                                                                                             */
/*******************************************************************************************/

/********************************************************************************************/
/*                                                                                                             */
/*                                          program.h                                                   */
/*  Jim Willis                                                                                            */
/*  Jan. 31, 2022                                                                                      */
/*                                                                                                            */
/*******************************************************************************************/

#define PROGRAMLINES    64

int timesThruTheTape = 0;

typedef struct
{
      int lineNumber;
      char writeIfZero;
      char directionIfZero;
      int go toIfZero;
      char writeIfOne;
      char directionIfOne;
      int go toIfOne;
      char writeIfBlank;
      char directionIfBlank;
      int go toIfBlank;
} PROGRAM;

//
// Turing program
//
// valid directions are Left, Right, Stay
// valid writes are 0, 1, _ blank
// 0 <= go to < PROGRAMLINES
//
// the next two control printing to console (DEBUG)
// #define PARITY
// #define COUNT_IN_BINARY

char *programName = "Parity and Count up in binary";

PROGRAM program[PROGRAMLINES] =
{
    // parity program
    {0, '0', 'L', 2, '0', 'L', 0, '0', 'L', 0}, // initiaize a blank tape to zeros
    {1, '0', 'L', 1, '1', 'L', 2, '_', 'L', 1}, // even parity, don't change contents
    {2, '1', 'L', 2, '0', 'L', 1, '_', 'L', 2}, // odd parity, change contents
    // count up in binary
    {3, '_', 'L', 3, '_', 'L', 3, '_', 'L', 3}, // write all blanks forever
    {4, '0', 'L', 4, '1', 'L', 4, '_', 'R', 5}, // move left until blank
    {5, '1', 'S', 4, '0', 'R', 5, '1', 'S', 4}  // move right and count
};

//
//  Turing machine
//   | -if 0--| -if 1--| -if _--|
//  #| W D ADR| W D ADR| W D ADR|
//_______________________________
//  0| 0 L   2| 0 L   0| 0 L   0|
//  1| 0 L   1| 0 L   2| _ L   1|
//  2| 1 L   2| 1 L   1| _ L   2|
//

extern int tapeIndex;
extern int programCounter;


/********************************************************************************************/
/*                                                                                                             */
/* int                                                                                                        */
/* process(char *tape, PROGRAM *program)                                                */
/*                                                                                                             */

uint64_t operations = 0;
int digit = 0;

int
process(char *tape, PROGRAM *program)
{
    int REGISTER;
    int j;
    
    REGISTER = readTape (tape, tapeIndex);
        
    if (REGISTER == ZEROTOKEN)
    {
        writeTape(tape, tapeIndex, program[programCounter].writeIfZero);
    
        if (program[programCounter].directionIfZero == 'R') 
        {
            tapeIndex++;
        }
        else if (program[programCounter].directionIfZero == 'L') 
        {
            tapeIndex--;
        }
        else if (program[programCounter].directionIfZero == 'S') 
        {
            // do nothing
        }

        programCounter = program[programCounter].go toIfZero;
    }
    else if (REGISTER == ONETOKEN)
    {
        writeTape(tape, tapeIndex, program[programCounter].writeIfOne);     

        if (program[programCounter].directionIfOne == 'R') 
        {
            tapeIndex++;
        }
        else if (program[programCounter].directionIfOne == 'L') 
        {
            tapeIndex--;
        }
        else if (program[programCounter].directionIfOne == 'S') 
        {
            // do nothing
        }
        
        programCounter = program[programCounter].go toIfOne;
    }
    else if (REGISTER == BLANKTOKEN)
    {
        writeTape(tape, tapeIndex, program[programCounter].writeIfBlank);       

        if (program[programCounter].directionIfBlank == 'R') 
        {
            tapeIndex++;
        }
        else if (program[programCounter].directionIfBlank == 'L') 
        {
            tapeIndex--;
        }
        else if (program[programCounter].directionIfBlank == 'S') 
        {
            // do nothing
        }
        
        programCounter = program[programCounter].go toIfBlank;
    }
    // tape wrap-around
    if (tapeIndex>=TAPEBYTES) 
    {
        tapeIndex=0;
        ++timesThruTheTape;
        
#ifdef PARITY       
        // print 16 tape squares
        for (j=0 ; j<16 ; ++j)
        {
            putchar(tape[tapeIndex+j]);
        }
        printf("\r");       
#endif
    }
    if (tapeIndex<0) 
    {
        tapeIndex = TAPEBYTES - 1;
        --timesThruTheTape; 
#ifdef PARITY   
        // print 16 tape squares
        for (j=0 ; j<16 ; ++j)
        {
            putchar(tape[tapeIndex-j]);
        }
        printf("\r");   
#endif
    }
#ifdef COUNT_IN_BINARY
    if (tapeIndex == 0 && programCounter == 4)
    {
        // print 80 tape squares backwards
        for (j=81 ; j>0 ; --j)
        {
            if (tape[j] != BLANKTOKEN) putchar(tape[j]);
        }

        printf("\r");
    }
#endif
    ++operations;
    
    if (programCounter == 4 && REGISTER == '_')
    {
        ++digit;
        printf("DIGITS= %02d Operations= %d\n", digit, operations);
    }
    
    return (REGISTER);
}

/*                                                                                                             */
/********************************************************************************************/

/********************************************************************************************/
/*                                                                                          */
/*                                          end program.h                                   */
/*                                                                                          */
/********************************************************************************************/

/********************************************************************************************/
/*                                                                                                              */
/*                                              tape.h                                                      */
/*  Jim Willis                                                                                             */
/*  Jan. 31, 2022                                                                                       */  
/*                                                                                                             */
/********************************************************************************************/

#define TAPEBYTES       4096


char tape[TAPEBYTES];
extern int tapeIndex;

/********************************************************************************************/
/*                                                                                                             */
/* int                                                                                                        */
/* readTape(char *tape, int tapeIndex)                                                      */
/*                                                                                                             */

int
readTape(char *tape, int tapeIndex)
{
    return(tape[tapeIndex]);
}

/*                                                                                                             */
/********************************************************************************************/

/********************************************************************************************/
/*                                                                                                             */
/* int                                                                                                        */
/* writeTape(char *tape, int tapeIndex, char writeChar)                             */
/*                                                                                                             */

int
writeTape(char *tape, int tapeIndex, char writeChar)
{
    tape[tapeIndex] = writeChar;
    
    if (writeChar==ONETOKEN)
    {
        HIGH (OUTPUT_WRITE);
    }
    else if(writeChar==ZEROTOKEN)
    {
        LOW (OUTPUT_WRITE);
    }
    else if(writeChar==BLANKTOKEN)
    {
        // do nothing
    }
    return(writeChar);
}
/*                                                                                                             */
/********************************************************************************************/

/********************************************************************************************/
/*                                                                                                             */
/*                                          end tape.h                                                   */
/*                                                                                                             */
/********************************************************************************************/



Post Reply