| Home > Lecture Notes > Turing |
Consider a "no frills" JavaScript language. I call it Bare Bones, based on that name from a different textbook (1). The idea is that anything not absolutely needed in the language is eliminated. While JavaScript is "loosely typed," Bare Bones knows nothing of types; its only type is "bit pattern of any length."
Bare Bones has 3 assignment statements and one control structure:
name is a variable name that can include any combination of one or more characters in the set {A-Z, a-z}. All statements are terminated with a semi-colon ( ; ), source program lines may contain multiple statements. Variables are created in memory the first time they are used; in the case of incr name and decr name, if name does not exist, it is created, initialized to 0, then the applicable operation performed.
The implementation of Bare Bones in the link below is designed to demonstrate the basic concepts in class; it is not a robust interpreter. Specifically, error checking is minimal at best.
Bare Bones Language Interpreter
Turing Machine examples in The Analytical Engine use a "unary" number system to represent integers. The number 3, for example, is represented by 3 1's, the number 5 by 5 1's, and so on. Also, the TM's in the book all start from the left edge of the tape. TM's can be designed in various ways. Consider representing numbers in binary. First we have to start from the right (least significant digit), and we need a concept of carrying overflow to the next most significant digit. Recall the half adder and full adder circuits from Chapter 7.
Turing Machine example, AE page 276
Note: Be sure to enclose the file name in quotes to ensure the browser does not munge the file name!Finally, as a last precaution, check the name of the downloaded files in Windows Explorer; if your browser named them TM*.dat.txt rename them TM*.dat.
Begin with "Russell's Paradox" (Bertrand Russell, 1872 - 1970):
In a certain town there is a male barber who shaves all those men, and only those men, who do not shave themselves. Question: Does the barber shave himself?
If the barber shaves himself he is a member of the class of men who shave themselves. Since no members of this class are shaved by the barber, we conclude that the barber does not shave himself. However, if the barber does not shave himself he is in the class of men who do not shave themselves. But the barber shaves all the men in this class, so we conclude that the barber does shave himself.
The answer to the question "Does the barber shave himself?" is neither yes or no. Therefore we have to conclude that the conditions described in the paradox cannot exist (at least in the world as we know it).
The textbook approaches the halting problem using TM serial numbers as input to TM's. Here is a more general, mathematical, presentation (2):
Theorem:
Proof (by contradiction):
[To show that no algorithm such as CheckHalt can exist, we will deduce a contradiction.]
Observe that the sequence of characters making up an algorithm X can be
regarded as a data set itself. Thus it is possible to consider running
CheckHalt with input ( X, X ). Define a new algorithm, Test, as follows:
Now run algorithm Test with input Test. If Test( Test ) terminates after a finite number of steps, then the value of CheckHalt( Test, Test ) is "halts", and so Test( Test ) loops forever. On the other hand, if Test( Test ) does not terminate after a finite number of steps, then CheckHalt( Test, Test ) prints "loops forever", and so Test( Test ) terminates. The two paragraphs above show that Test( Test ) loops forever and also that it terminates. This is a contradiction. But the existence of Test follows logically from the supposition of the existence of an algorithm CheckHalt that can check any algorithm and data set for termination. [Hence the supposition must be false, and there is no such algorithm.] |
Some additional Alan Turing links