Contents

✓ Impact On Programming Language Design

TM has introduced a number of concepts that have a deep and long lasting impact on programming language design.

Architecture

  • General purpose computer

    The universal TM.

  • CPU

    The control logic of the UTM.

  • Memory

    The tape of the UTM

  • Code region of memory

    The initialization of the UTM tape with the simulated TM’s control logic.

  • Input region of memory

    The initialization of the UTM tape with the simulated TM’s tape content.

Data structures

  • Arrays

    Tape of TM

  • Serialization

    Encoding of abstract data into strings

  • Array getter and setter

    Read and write using the head of the TM

Programming constructs

  • Variables

    A specific cell or cells on the tape

  • Pointers

    Cells that contain indexes of other cells of the tape

  • Statements

    States of the control logic

  • GOTO instruction

    State transition

  • Subroutines

    Sub-automaton of the control logic

Programming style

  • Mutable data structures

    Tape is to be updated and erased

  • Procedural programming

    Automaton executes sequences of instructions

  • Binary I/O

    Tape can only hold symbols in a linear fashion, so all data structures must be encoded into strings