Input/Output Tape | Terms in Series |

0b1;1; | 1, 1 |

0b1;1;11; | 1, 1, 2 |

0b1;1;11;111 | 1, 1, 2, 3 |

0b1;1;11;111;11111; | 1, 1, 2, 3, 5 |

0b1;1;11;111;11111;11111111; | 1, 1, 2, 3, 5, 8 |

**1.0 Introduction**

I thought I would describe the program for a specific Turing machine. This Turing machine computes the Fibonacci sequence in tally arithmetic, as illustrated in Table 1 above. The left-hand column shows the tape for the Turing machine for successive transitions into the Start state. (The location of the head is indicated by the bolded character.) The right-hand column shows a more familiar representation of a Fibonacci sequence. This Turing machine never halts for valid inputs. It can calculate other infinite sequences, such as specific Lucas sequences, for other valid inputs.

A Turing machine is specified by the alphabet of characters that can appear on the tape, possible valid sequences of characters for the start of the tape, the location of the head at the beginning of a computation, the states and the state transition rules, and the location of the state pointer at beginning of a computation.

**2.0 Alphabet**

Symbol | Number OfOccurrences | Comments |

0 | 1 | Start of tape marker |

b | Potentially Infinite | Blank |

; | Potentially Infinite | Symbol for number termination |

1 | Potentially Infinite | A tally |

x | 1 | For internal use |

y | 1 | For internal use |

z | 1 | For internal use |

**3.0 Specification of Valid Input Tapes**

At start, the (input) tape should contain, in this order:

- 0, the start of tape marker.
- b, a blank.
- Zero or more 1s.
- ;, a semicolon.
- One or more of the following:
- Zero or more 1s.
- ;, a semicolon.

The head shall be at a blank or semicolon such that exactly two semicolons exist in the tape to the right of the head. Table 3 provides examples (with the head being at the bolded character).

0b;; |

0b1;; |

0b1;1; |

0b11;1; |

0b1;1;11;111;11111;11111111; |

**4.0 Definition of State**

The states are grouped into two subroutines, CopyPair and Add. Error is the only halting state, to be entered when an invalid input tape is detected. The Turing machine begins the computation with the state pointer pointing to the Start state, in the CopyPair subroutine. Eventually, the Turing machine enters the PauseCopy state. The machine then transitions to the StartAdd state, in the Add subroutine. Another number in the sequence has been successfully appended to the tape when the Turing machine enters the PauseAdd state.

The Turing machine then transitions into the Start state. The CopyPair and Add subroutines are repeated in pairs forever.

**4.1 CopyPair**

The input tape for the CopyPair subroutine is any valid input tape, as described above. The state pointer starts in the Start tape. Error is the only halting state. The subroutine exits with a transition from the PauseCopy state to the StartAdd state. When the PauseCopy state is entered, the tape shall be in the following configuration:

- The terminal semicolon in the tape, when the Start state was entered, shall be replaced with a z.
- The head shall be at that z.
- The tape to the right of the z shall contain a copy of the character string to the right of the head when the Start state was entered.

This subroutine can be implemented by the states described in Table 4. The detailed implementation of each state is provided in the appendix. Throughout these states, there are transitions to the Error state triggered by encountering on the tape a character that cannot be there in a valid computation.

State | Description |

Start | Moves the head forward one character. |

ReadFirstChar | Replaces first ; or 1 (after position of head when the subroutine was called) with x or y, respectively. |

WriteFirstSemi | Writes a ; at the end of the tape. Transitions to GoToTapeEnd. |

WriteFirstOne | Writes a 1 at the end of the tape. Transitions to GoToTapeEnd. |

GoToTapeEnd | Moves the head backward one character to locate the head at the character that was at the end of the tape when the subroutine was called. |

MarkTapeEnd | Replaces original terminating ; with z. |

NexChar | Replaces the x or y on the tape with ; or 1, respectively. |

StepForward | Moves the head forward one character. |

ReadChar | Replaces the next ; or 1 with x or y, respectively. |

WriteSemi | Writes a ; at the end of the tape. Transitions to NextChar. |

WriteOne | Writes a 1 at the end of the tape. Transitions to NextChar. |

WriteLastSemi | Writes a ; at the end of the tape. Transitions to SetHead. |

SetHead | Moves head to the z on the tape. |

PauseCopy | For noting that last two numbers on the tape, when the subroutine was called, have been copied to the end of the tape. |

**4.2 Add**

When the PauseAdd state is entered, the tape shall be in the following configuration:

- The semicolon between the z and the last semicolon, when the StartAdd state is entered, shall be replaced by a 1, if there is at least one 1 between this character and the terminating semicolon.
- The semicolon at the end of the tape, when the StartAdd state is entered, shall be erased (replaced by a blank).
- The character before the erased semicolon shall be replaced by a semicolon.
- The z shall be replaced by a semicolon.
- The head shall be at a semicolon such that two semicolons exist to the right of the head.

State | Description |

StartAdd | Moves the head forward one character. |

FindSemiForDele | Replaces the ; mid-number with 1. |

FindSumEnd | Erases terminating ;. |

EndSum | Writes terminating ; at the tape position one character backwards. |

FindSumStart | Replaces z with ;. |

StepBackward | Moves the head backwards one character. |

ResetHead | Set head to previous ;, before the ; just written. |

PauseAdd | For noting next number in Fibonacci series. |

**5.0 Length of Tape and the Number of States**

After three run-throughs of this Turing machine, five numbers in the Fibonacci sequence will be calculated. And the tape will contain 19 characters. As shown in Table 6, the number of states is 22. For the group activity I have defined for simulating a Turing machine, 42 people are needed. (One more person is needed, in computing the next number in the sequence, to be erased from the tape than ends up as characters on the tape.) I suppose one could get by with 36 people, if one is willing to some represent two states, one in each subroutine.

Subroutine | Number OfStates | State Names |

CopyPair | 15 | Error, Start, ReadFirstChar, WriteFirstSemi, WriteFirstOne, GoToTapeEnd, MarkTapeEnd, NextChar, StepForward, ReadChar, WriteSemi, WriteLastSemi, SetHead, WriteOne, PauseCopy |

Add | 7 | StartAdd, FindSemiForDele, FindSumEnd, EndSum, FindSumStart, StepBackward, PauseAdd |

Total | 22 |

**Appendix A: State Transition Tables**

**A.1: The CopyPair Subroutine**

Start | ReadFirstChar | |||||

0 | 0 | Error | 0 | 0 | Error | |

b | Forwards | ReadFirstChar | b | b | Error | |

; | Forwards | ReadFirstChar | ; | x | WriteFirstSemi | |

1 | 1 | Error | 1 | y | WriteFirstOne | |

x | x | Error | x | x | Error | |

y | y | Error | y | y | Error | |

z | z | Error | z | z | Error |

WriteFirstSemi | WriteFirstOne | |||||

0 | 0 | Error | 0 | 0 | Error | |

b | ; | GoToTapeEnd | b | 1 | GoToTapeEnd | |

; | Forwards | WriteFirstSemi | ; | Forwards | WriteFirstOne | |

1 | Forwards | WriteFirstSemi | 1 | Forwards | WriteFirstOne | |

x | Forwards | WriteFirstSemi | x | Forwards | WriteFirstOne | |

y | Forwards | WriteFirstSemi | y | Forwards | WriteFirstOne | |

z | z | Error | z | z | Error |

GoToTapeEnd | MarkTapeEnd | |||||

0 | 0 | 0 | Error | |||

b | b | b | Error | |||

; | Backwards | MarkTapeEnd | ; | z | NextChar | |

1 | Backwards | MarkTapeEnd | 1 | 1 | Error | |

x | x | x | Error | |||

y | y | y | Error | |||

z | z | z | Error |

NextChar | StepForward | |||||

0 | 0 | Error | 0 | |||

b | b | Error | b | |||

; | Backwards | NextChar | ; | Forwards | ReadChar | |

1 | Backwards | NextChar | 1 | Forwards | ReadChar | |

x | ; | StepForward | x | |||

y | 1 | StepForward | y | |||

z | Backwards | NextChar | z |

ReadChar | WriteSemi | |||||

0 | 0 | Error | 0 | 0 | Error | |

b | 1 | Error | b | ; | NextChar | |

; | x | WriteSemi | ; | Fowards | WriteSemi | |

1 | y | WriteOne | 1 | Forwards | WriteSemi | |

x | x | Error | x | Forwards | WriteSemi | |

y | y | Error | y | Forwards | WriteSemi | |

z | z | WriteLastSemi | z | Forwards | WriteSemi |

WriteLastSemi | SetHead | |||||

0 | 0 | Error | 0 | 0 | Error | |

b | ; | SetHead | b | b | Error | |

; | Forwards | WriteLastSemi | ; | Backwards | SetHead | |

1 | Forwards | WriteLastSemi | 1 | Backwards | SetHead | |

x | Forwards | WriteLastSemi | x | x | Error | |

y | Forwards | WriteLastSemi | y | y | Error | |

z | Forwards | WriteLastSemi | z | z | PauseCopy |

WriteOne | PauseCopy | |||||

0 | 0 | Error | 0 | |||

b | 1 | NextChar | b | |||

; | Forwards | WriteOne | ; | |||

1 | Forwards | WriteOne | 1 | |||

x | Forwards | WriteOne | x | |||

y | Forwards | WriteOne | y | |||

z | Forwards | WriteOne | z | z | StartAdd |

**A.2: The Add Subroutine**

StartAdd | FindSemiForDele | |||||

0 | 0 | |||||

b | b | |||||

; | ; | 1 | FindSumEnd | |||

1 | 1 | Forwards | FindSemiForDele | |||

x | x | |||||

y | y | |||||

z | Forwards | FindSemiForDele | z |

FindSumEnd | EndSum | |||||

0 | 0 | |||||

b | Backwards | EndSum | b | Backwards | EndSum | |

; | b | EndSum | ; | b | EndSum | |

1 | Forwards | FindSumEnd | 1 | ; | FindSumStart | |

x | x | |||||

y | y | |||||

z | z |

FindSumStart | StepBackward | |||||

0 | 0 | |||||

b | b | |||||

; | Backwards | FindSumStart | ; | Backwards | ResetHead | |

1 | Backwards | FindSumStart | 1 | |||

x | x | |||||

y | y | |||||

z | ; | StepBackward | z |

ResetHead | PauseAdd | |||||

0 | 0 | |||||

b | b | |||||

; | ; | PauseAdd | ; | ; | Start | |

1 | Backwards | ResetHead | 1 | |||

x | x | |||||

y | y | |||||

z | z |

**A.3: Modifications?**

The above is my first working version. I have not proven that cases can never arise where I have not specified rules in the tables for the states for the Add subroutine. Nor do I know that all rules can be triggered by some, possibly invalid, input tape. I know that I have not defined the minimum number of states for the system. For example, the ReadChar state could be defined as in Table A-12, along with the elimination of the WriteLastSemi and SetHead states. This would result in the CopyPair subroutine specification not being met and a tighter coupling between the two subroutines. On the other hand, the subroutines are already coupled through the appearance of z on the tape during the transition from one subroutine to the other.

ReadChar | ||

0 | 0 | Error |

b | 1 | Error |

; | x | WriteSemi |

1 | y | WriteOne |

x | x | Error |

y | y | Error |

z | z | PauseCopy |

## No comments:

Post a Comment