This post describes another program for a Turing Machine. This Turing machine implements a binary counter (Table 1). I do not think I am being original here. (Maybe this was in the textbook on computability and automata that I have been reading.)2.0 Alphabet
|0||Potentially Infinite||Binary Digit Zero|
|1||Potentially Infinite||Binary Digit One|
3.0 Specification of Valid Input Tapes
At start, the (input) tape should contain, in this order:
- t, the start-of-tape symbol.
- b, a blank.
- A sequence of binary digits, with a length of at least one.
The above specification allows for any number of unnecessary leading zeros in the binary number on the tape. The head shall be at the blank following the start-of-tape symbol.4.0 Specification of State
The machine starts in the Start state. Error is the only halting state. Table 3 describes some conditions, for a non-erroneous input tape, that states are designed to satisfy, on entry and exit. For the states GoToEnd, FindZero, CreateTrailingOne, Increment, and ResetHead, the Turing machine may experience many transitions that leaves the machine in that state after the state has been entered. When the state PauseCounter has been entered, the next increment of a binary number appears on the tape.
|On Entry||On Exit|
|Start||The head is immediately to the left of the binary number on the tape. (The binary number on the tape at this point is referred to as "the original binary number" below.)||Same as the entry condition for GoToEnd.|
|GoToEnd||The head is under the first digit of the binary number on the tape.||Same as the entry condition for FindZero.|
|FindZero||The head is under the last digit of the binary number on the tape||If all digits in the original binary number are 1 and that number has not been updated with a leading zero, the head is under the first digit of the binary number on the tape. If the original binary number contained at least one digit 0, the head is under the location of the last instance of 0 in the original binary number, and that digit has been changed to a 1. Otherwise, the head is under the first digit in the binary number now on the tape, and that digit is now a 1 (having once been a leading zero).|
|CreateLeadingZero||All the digits in the original binary number are 1. The head is under the first digit of the binary number on the tape.||Same as the entry condition for CreateTrailingOne|
|CreateTrailingOne||All the digits in the original binary number are 1. The first digit in the original binary number has been replaced by 0. The head is under that first digit.||The original binary number has been shifted one digit to the left, and a leading zero has been prepended to it. The head is under the last digit of the binary number now on the tape.|
|StepForward||If all digits in the original binary number are 1, that number has been shifted one digit to the left, that number has been updated with a leading 0 which is now a 1, and the head is under that digit. Otherwise, the last instance of 0 in the original number has been updated to a 1, and the head is now under that digit tape.||Same as the entry condition for Increment.|
|Increment||If all digits in the original binary number are 1, that number has been shifted one digit to the left, that number has been updated with a leading 0 which is now a 1, and the head is under the next location on the tape. Otherwise, the last instance of 0 in the original number has been updated to a 1, and the head is now under the next location on the tape.||Same as the entry condition for ResetHead. All the 1's to the right of the 0 updated to a 1 have themselves been updated to a 0.|
|ResetHead||The head is under the last digit of the binary number on the tape, and that number is the successor of the original binary number.||Same as the entry condition for PauseCounter.|
|PauseCounter||The head is immediately to the left of the binary number on the tape, and that number is the successor of the original binary number.|
I think one could express the conditions in the above lengthy table as logical predicates. And one could develop a formal proof that the state transition rules in the appendix ensure that these conditions are met on entry and exit of the non-halting tape, at least for non-erroneous input tapes. I do not quite see how invariants would be used here. (When trying to think rigorously about source code, I attempt to identify invariants for loops.)5.0 Length of Tape and the Number of States
Suppose the state PauseCounter was a halting state. Then this Turing machine would be a linear bounded automaton. In the Chomsky hierarchy, automata that accept context-sensitive languages need not be more general than linear bound automata.
The program for this Turing machine consists of 10 states. The number of characters on the tape grows at the rate O(log2 n), where n is the number of cycles through the start state. I gather the above instructions could be easily modified to not use any start-of-tape symbol. Anyways, 20 people seems more than sufficient for the group activity I have defined, for this particular Turing machine.Appendix A: State Transition Tables
This appendix provides detail specification of state transition rules for each of the non-halting states. I provide these rules by tables, with each table showing a pair of states.