## Monday, May 16, 2016

### A Turing Machine for a Binary Counter

 Input/Output Tape Decimal tb0 0 tb1 1 tb10 2 tb11 3 tb100 4 tb101 5

1.0 Introduction

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

 Symbol Number OfOccurrences Comments t 1 Start-of-tape Symbol b Potentially Infinite Blank 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.

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.

 Start GoToEnd t t Error t t Error b Forwards GoToEnd b Backwards FindZero 0 0 Error 0 Forwards GoToEnd 1 1 Error 1 Forwards GoToEnd
 FindZero CreateLeadingZero t t Error t t Error b Forwards CreateLeadingZero b b Error 0 1 StepForward 0 0 Error 1 Backwards FindZero 1 0 CreateTrailingOne
 CreateTrailingOne StepForward t t Error t t Error b 1 FindZero b b Error 0 Forwards CreateTrailingOne 0 0 Error 1 Forwards CreateTrailingOne 1 Forwards Increment
 Increment ResetHead t t Error t t Error b Backwards ResetHead b b PauseCounter 0 Forwards Increment 0 Backwards ResetHead 1 0 Increment 1 Backwards ResetHead
 PauseCounter t t Error b b Start 0 0 Error 1 1 Error