CSCI 381 Goldberg Lecture 2: Turing's Theory of Computation: Effectiveness and Processes
Administrative Updates
Section titled “Administrative Updates”Grade Codes
An email was sent with your Grade Code. Find it on the Brightspace system under “QUIZZES”. Do not share this string with anyone else, as grades will be distributed using it.
Brightspace Usage
I use the QUIZZES format to collect student responses—note that this does not necessarily count as a quiz. Failure to submit gets a 2% penalty off your total grade at the end of the semester.
I use Brightspace for collection of student responses and uploading of assignments when due, but not for grading. Grading is done manually (after downloading collected data), and grades are emailed to the class based on the Grade Code selected.
Your Grade Code will be available throughout the semester under the Brightspace Quizzes section.
Lecture Content
Section titled “Lecture Content”Effective vs. Efficient Computation
Section titled “Effective vs. Efficient Computation”Effective Computation (Turing’s focus) = whether a computation halts/concludes. Does not concern time/space complexity.
Efficient Computation = optimizing time and space resources. Focus of Analysis of Algorithms.
Turing was interested in solvability (does the problem have a solution at all?), not efficiency (how fast?).
Critical Systems and Infinite Loops
Section titled “Critical Systems and Infinite Loops”Yet, Critical systems are supposed to continuously run and therefore must contain infinite loops.
Medical monitoring machine; nuclear reactor temperature monitor; elevators in the building; airplane control; radar Y2K = Year 2K = Year Two Thousand (2000).
Intel made computer boards and chips for IBM personal computers, storing dates using only the last two digits (e.g., 1999 as “99”) to save memory in the 1980s. They didn’t expect boards to last until 2000 (the penalty of success—products so reliable people kept using them for 10-15 years).
On January 1, 2000, the stored digits would be “00” = 0, which is less than 99 (the previous year). Critical monitoring systems compare date differences; a negative time difference could crash systems. Companies invested heavily prewriting systems before Y2K. While most were preemptively fixed, a few problems occurred: an elevator in Australia stopped, one airport experienced minor airplane control glitches.
So, what is the difference between algorithms (finite number of steps) and critical monitoring systems (runs infinitely)? Of course, critical systems contain algorithms.
Algorithms vs Processes
Section titled “Algorithms vs Processes”Algorithm = finite sequence of steps solving a single problem instance. Each execution halts after an input.
Process = infinite loop “driving” an algorithm, continually applying it to new, independent inputs.
Example (Verizon “Can you hear me now?”): The algorithm answers the question once; the process repeats it infinitely at different locations as conditions change.
In Operating Systems: Processes called daemons run infinitely in background (e.g., polling the hardware—continuously listening for signals). The system doesn’t know when events occur, so the daemon must always be ready.
The Paradox Resolved: An algorithm requires finite steps; a process requires infinite operations. Both are necessary. Critical systems must decide about instances in finite time, but be ready at all times. Each problem instance is analyzed in finite steps, but instances arrive infinitely.
Input and Output in Computation
Section titled “Input and Output in Computation”The Mathematical vs. Turing Perspective:
Mathematically, functions map values to values. Turing maps memory configurations to memory configurations. Turing cares not whether output is correct, but whether the computation halts.
GIGO (Garbage In, Garbage Out): Turing was unconcerned with whether code solved the intended problem correctly. If code is error-prone or badly implemented, but it halts, Turing considers it effective/solvable.
Turing’s Definition of Input/Output:
Memory storage (tape) prior to execution = input
Memory storage (tape) after halting = output
An irony: an effective computation can only use a finite portion of the infinite tape (continuous reading/writing causes infinite loops). The entire memory configuration is treated as a single natural number.
Critical Point: Output only exists if the machine halts. This includes if the machine stops due to crashing or exceptions. Whatever is in memory becomes the output.
To a mathematician: function maps separate input/output data. To Turing: a program maps the entire memory configuration before execution to the entire memory configuration after execution.
The Natural Numbers Starting with Zero
Section titled “The Natural Numbers Starting with Zero”Programming Reason: Array names store the base address; the index is an offset. The first cell has address = base + 0 offset, making zero the natural starting index.
Theoretical Reason (Turing’s): Since a program maps memory configurations as single natural numbers, and a mathematical function must be defined for all inputs, Turing’s machine must map the all-zeros memory configuration (the natural number 0). The entire memory is treated as one continuous natural number, so zero must be included. This is why computer theory requires natural numbers to start with 0, not 1.
Space vs. Time in Theory and Practice:
Early theory prioritized space resources (memory efficiency). Turing marginalized space so he could focus on solvability (does the machine halt?).
Modern Analysis of Algorithms prioritizes time efficiency because computational memory is now abundant.
The shift reflects practical change: space was once scarce (hence a concern), time is now the limiting factor.
Turing provided infinite tape to never worry about memory limits. The irony: effective computation only uses finite tape (halting ensures this). The infiniteness is protection against unknown memory needs, not intended for actual use.
Program as Function and Mathematical Mappings
The mathematical perspective of our notion of a program (code) is that of function and mathematical mappings.
Simplistically, a program receives an input, processes this input and yields an output. To the theorists the mapping conducted by the program is from the current configuration of memory storage (defined in totality as “input” and contains within what is the actual input to the problem at hand) and is then mapped to the new configuration of memory storage (termed the output, but again contains within that which the problem needs as “output”). To Turing, the entire “tape” (memory storage) is the input and the entire “tape” after the program halts is considered the “output”. In order that stray values not remain on the tape at start and finish, Turing required that at the start and finish the tape should be blank except for the input at the start and the actual output at the finish. Since only a finite number of tape cells are actually involved in the storage of values, input and/or outputs, the ENTIRE string of cells at any given step of the computation, can be considered as a number with a finite number of digits. This can be considered “encoded” by a natural number. This understanding then really does package the computational process as a function from one number (encoded memory storage containing the input) to another single number (subsequent encoded memory storage containing the output).