What Can be Computed?

This project will look at Finite State Machines, one of the foundations of computing. We’ll provide some background on why these are important in Background. In The Turing Machine we’ll discuss the Turing Machine in some detail. We’ll provide an example in Example Machine.

The essential exercise is to write the necessary Python software to emulate a Turing Machine. We’ll look at the implementation closely in Turing Machine Implementation. Exercise 1 is the first set of programming exercises.

In Test Machines we’ll look at some basic Turing Machine specifications that we can use for testing. Exercise 2 will implemnet some of those additional machines to act as confirmation and as unit tests.

As a digression, we’ll provide additional background in Consequences. This background answers some of the questions raised in the Background section.

We can then look at further applications of Finite State Machines in Other Applications. This includes some simple lexical scanning and parsing applications.

We’ll look at some variations on the implementation of our Turning Machine in Alternative Specifications

Background

In the 1930’s – at the very dawn of digital computation – mathematician Alan Turing wondered what numbers could be computed by a digital computer. Indirectly, he was wondering what should a computer be designed to do. What was a sensible set of constraints or parameters around computer and programming language?

At that time “computer” was a person’s job title. A mathematician, like Alan Turing, would create worksheets for people to use in computing a particular result. Turing worked on code breaking during World War II, and his “computers” were people who carried out rather complex analyses of coded messages. Turing prepared the instructions and worksheets for his computers to decode intercepted messages.

The question of computable numbers – to modern programmers – can seem a bit silly. The unthinking answer is that digital computers can represent any number.

But we have a bit of a problem. Mathematicians have identified a pretty wide variety of numbers. Can we represent all rational fractions? What about all irrational decimals? What about all complex numbers? Are there yet other kinds of numbers that a computer can’t represent?

The essential question is “what numbers should we be able to compute with Python?”

Python. This essential computability question defines how we design computer hardware and how we design programming languages. The first step, then is to define what is computable. Clearly, a language like Python must have some minimal set of features. Further, there must be some standard of “computability” that a language designer must respect in creating the language. In the next section, we’ll look at the subject of computability.

Once we agree on what is computable, we can then match a given programming language (e.g., Python) against the definition to see if our programming language is complete. This sounds like a daunting, heavy-weight mathematical proof, but actually, it’s relatively simple. In this section, we’ll construct the proof that Python is a complete language. Really.

The definition of “computable” is based on a hypothetical model of a “computer”. We can (and will) build that hypothetical computer model in Python. The Python program that implements the hypothetical computer is the constructive proof that the Python language completely fits the hypothetical model of computability.

The essential notion of computability is based on the idea of computable numbers. So we’ll look at those briefly.

Numbers. A common mistake is to claim that there are just “numbers”. This is clearly untrue. We can easily define “natural” numbers with a pleasant set of axioms. We can say that we have a first number, call it “0”. We can define a successor numbers, and the properties of equality and create an infinite set of numbers. Yes, there are an infinite set of numbers. But we have this concept of successor, so – in principle – we can count this set.

Interestingly, this set doesn’t include negative numbers. Okay, fine, we’ll add negative numbers to our infinite set of natural numbers, and we have a larger infinite set of numbers. Turns out, we can work out a mapping from natural numbers to signed numbers. This makes the set of signed integers “countably infinite”.

The long class is a physical implementation of this abstact concept of signed natural number. Also, the decimal.Decimal class, with a fixed decimal point, is essentially the same kind of number.

This set of integers doesn’t include any fractions. We can easily define an infinite set of fractions using any two of our infinite set of natural numbers. This gives us a set of rational numbers that’s obviously also infinite. It seems to be a larger set, but we can work out a mapping from natural numbers to rational fractions. This makes the rational numbers “countably infinite”, also.

The Rational class (see Rational Numbers) is an implementation of this abstract concept of rational number.

Yet More Numbers. The set of rational numbers, however, still isn’t the final word. We can define some “algebraic numbers”, which are solutions to equations that aren’t rational nunmbers. For instance, solving this polynomial for , . The answer is ; no rational number can satisfy this. This means that there must be “irrational” numbers.

We can combine the irrational and rational numbers into a big set of numbers, commonly called “real” numbers.

If we start writing down numbers as long strings of decimal digits (or binary bits) we can – with some cleverness – create numbers that we cannot easily map to the natural numbers. This means that infinite decimal fractions form a larger set of numbers that’s “uncountably infinite”. Rats.

The float class is a finite implementation these infinite binary fractions. Since the float class is actually finite, it suffers from some practical limitations, but, in spirit, it is intended to follow this kind of number.

We’re still not done. solving this polynomial for , , leads us to complex numbers.

Okay. Fine, there are a lot of numbers. The first question is, “are all of these computable?” Essentially, we are also asking “can we define ‘computable’?” We’d really like a constructive definition of computable that matches our vague notions of what a computer should do.

Profound Limitations. For purposes of simplification, we need to set aside the “finite” part of physical computers and discuss a hypothetical infinite computer. Why should talk about theoretical computers?

The idea behind this is to divorce a simple, formal definition of computer from any specific and complex piece of hardware. If we try to discuss specific pieces of hardware, we have lots of weird limitations and gotchas based on limited memory, available power, limited desktop space, dissipation of heat, radio-frequency interference, laws of physicas, etc.

The point is to first talk about what’s possible before talking about what’s practical. Before we even start, we need to know if there any profound limitations on what’s possible. Since the answer is “yes”, there are theoretical limitations, we need to know exactly what those limitations are.

Goals. Fundamentally, the overall goal has two parts.

1. Show that there is a Turing Machine which can compute any particular mathematical function. This defines the theoretical possibilities for computable numbers. We’ll skip over this.
2. Create a Python implementation of a Turing machine. This will establish that the Python language is – in principle – capable of all the theoretical computations.

We’ll trust the mathematicians that the Turing Machine’s computable numbers are a good match for what we understand numbers to be. It turns out that the match isn’t perfect; we’ll look at this briefly in Consequences.

The Turing Machine

To talk about computability, we need a general-purpose (and simple) model for a computer. We need something that we can define clearly and completely. We also need something that captures what we mean by “compute”. We need input, output, state change, and some kind of “program” to control those state changes.

We’ll call our theoretical computer a Turing Machine, naming it after mathematician Alan Turing.

The essential feature of all computation is state change. We introduced the idea in Variables, Assignment and Input. Therefore, a hypothetical computer must have some current internal state and some rules for changing the internal state based on inputs.

This internal state is as simple as flag or marker that identifies which transition rules are active. If we were to number each rule, the state would be the current rule number. If we had a person following instructions on a worksheet, we might ask them to put a removable sticky-note on the step they were following so they wouldn’t lose their place.

In addition to internal state, we need some form of input, output and (possibly) working memory. Turing’s idea was to use an infinitely long tape for this. [Infinite? Yes. It’s an abstraction; we need to define the set of countably infinite numbers, so we need an infinite tape.]

The idea is that we can mark the tape with some values, start the machine processing. When it stops, we can look at the tape to see the answer.

Alphabet. Our machine must be able to record state on the tape. We need to define some alphabet of symbols. A minimal alphabet is two distinct symbols and nothing more. We could use X and O or and . We could use a larger alphabet of the 128 ASCII characters that Python uses. Or we could use the vast library of Unicode symbols.

The only restriction is that the symbols are distinct and the alphabet of symbols is limited and known in advance. For now, we’ll stick to just two symbols.

The Tape. Our Turing machine, then, has as it’s visible component, a tape which shuttles back and forth under a read/write station. Or, we could think of a little read/write device that walks up and down a long tape laid out on the floor of a vast building.

There are some great YouTube videos of Turning Machines. Feel free to watch those for a better sense of that a Turing Machine might be like.

The interesting part is the “current” position of the read/write device relative to the tape itself. Here’s a sample tape with a few symbols. We’ll use brackets to show where the read/write device is positioned.

Clearly, this alphabet includes at least the symbols: .

Also, the current position is the fourth one on the tape.

The Rules. Our Turning Machine has an internal state to remember where it is, an infinite tape that is input, output and working memory. It also has some rules for deciding what to do. To keep things simple, each rule includes the following things:

• Symbol. This is the symbol to be matched against the current symbol on the tape. Since the alphabet is finite, we’ll have one rule per symbol.
• Write. Write a new symbol or do no writing, leaving the tape unchanged. A purist could argue that writing the matched symbol back to the tape is the same as not writing.
• Move. The machine can move the tape forward one, backward one, or not at all.
• Next State. This next state is the same or different collection of rules.

This can be simplified. It can also be made more complex. We’ll look at some alternatives below. For now, this will give us enough to work with.

For a give state, we have a set of rules that specifies the moving and writing for each possible symbol. If we have a small alphabet of just two symbols, each state has only two rules. If we have a larger alphabet, each state must have a larger number of rules.

Halting. It’s sometimes helpful to have a special rule to stop the machine from further processing. This halt rule is simply a special case rule that doesn’t have a next state. Instead of going to a next state, the machine stops working.

A rule that doesn’t write, doesn’t move and specifies no state change must halt, since the machine will stay in that state forever.

Example Machine

Let’s use a very small alphabet of and .

We’ll define a very simple machine to check the “parity” of a tape. We want to be sure that number of symbols is even. If it’s odd, we’ll write an extra symbol. If it’s even, we’ll write an extra .

This kind of algorithm is used with 7-bit ASCII characters to create 8-bit even-parity for transmission across noisy wires. If the received 8-bit value does not have even parity, the character is ignored.

Here are the two states.

0. Even. If : write nothing, move tape forward, change to state 1.

   If : write nothing, move tape forward, stay in state 0.

   If blank: write , change to state 2.

1. Odd. If : write nothing, move tape forward, change to state 0.

   If : write nothing, move tape forward, stay in state 1.

   If blank: write , change to state 2.

2. Halt. For all symbols, write nothing, do not move, change to state 2.

Let’s look at how this works with a sample tape.

1. The machine starts in the State 0. The tape has five symbols, and we’re positioned at the start. This is the starting condition.

   

2. The state is State 0. The symbol is , so the machine moves the tape forward and switches to State 1.

   

3. The state is State 1. The symbol is , so the machine moves the tape forward and switches to State 0.

   

4. The state is State 0. The symbol is , so the machine moves the tape forward and stays in State 0.

   

5. The state is State 0. The symbol is , so the machine moves the tape forward and switches to State 1.

   

6. The state is State 1. The symbol is , so the machine moves the tape forward and stays in State 1.

   

7. The state is State 1 and the tape is blank: the machine moves th etape forward, writes and changes to State 0.

   

8. The state is State 0 and the tape is blank: the machine writes a and changes to State 2.

   

9. In State 2, the machine halts. There are an even number of on the tape.

   

Turing Machine Implementation

Our job is to write a Python script that simulates this kind of Turing Machine. The existence of such a script is proof that the Python language does everything a Turing Machine does. (Separately, we need to prove that a Turing Machine does everything that a mathematician could ever want.)

We’ll need a model of the tape. A Python list can accomplish this nicely, we can populate the list with symbols like this:

tape = [ 'X', 'X', 'O', 'X', 'O', None, None, None ]

By adding a bunch of blank cells at the end of the tape, we can simplify our implementation. Theoretically, we have an infinite number of blank cells on the tape; therefore a well-written Turing Machine program will simply appned empty cells to the list as long as necessary. To get started, though, it’s easy to simply pad the tap with blank cells.

We’ll need a model of the rules. Each rule can be encoded as a tuple (or namedtuple) that has the required state change: the tape movement, symbol to write and the next state.

Rule = namedtuple( 'Rule', ['write', 'move', 'state'] )

For the write attribute, we can provide the symbol to be written, or None if nothing is to be written.

For the move attribute, we can use the values +1, -1 or None.

For the state attribute, we can provide the number of the next state, or None if the machine should halt.

We can then code each state of our machine as a dictionary of rules that map a symbol on the tape to a state change tuple that shows what to do.

rule_0_map = {
    'X': Rule(None,+1,1),
    'O': Rule(None,+1,0),
    None: Rule(None,None,None) }

We can then code our transition rules as a whole as a dictionary that maps rule numbers to rules.

transitions = {
    0: rule_0_map,
    1: rule_1_map,
}

In order to simulate a Turing Machine, we need the following things:

• The initial tape.
• The transitions, which is a dictionary that maps a state to a set of rules. Each rule maps a tape symbol to a state change.
• A starting state number and starting tape position.

A relatively simply Python function can then step through this Turning machine cycle until the machine halts.

Turing Machine Function

Let T be a tape, a list of symbols.

Let M be the complete set of machine states and rules, . Each state is set of rules mapping from a symbol, C, to a state change, . Each state change, specifies what symbol to write, w, what direction to move, m, and the next state, r.

1. Initialize. Set the initial tape position, P to 0, the start of the tape. Set the current state, S to state 0.

2. Cycle. While the machine’s state is not the halt state of None.

   1. Eval. Set C to the symbol at the current position, P, on the tape, T.

      Given current state, S, and current symbol, C, determine which state change to use.

   2. Apply. Given the state change, , do the following.

      • If indicated, write the requested symbol, w, in the new position. This updates the tape, T and the current position, P.

      • Move the tape in the appropriate direction. This updates the current position, P: next is , previous is . No movement is None.

        Moving the tape to the next position may require extending the tape’s list object to add a blank cell.

      • Set the current state, S, to the next current state, r.

   3. Log. Optionally, print the current state of the machine to a log.

3. Display. Print the final state and final content of the tape.

Exercise 1

1. Define a function that implements the basic Turing Machine.

   turing(transitions, tape)

   Accepts a dictionary of transition rules and an input tape. Starts in rule 0 with tape at position 0. Executes the various transitions until the machine reaches a transition where the next state is None, then it halts.

   Prints a log showing the tape as it moves and changes.

2. Create a set of transitions to do the “Even X” processing. If the number of “X”s on the tape even, halt. If the number of “X“‘s on the tape is odd, append an “X” and halt.

Test Machines

The point of defining this Turing Machine is to define what’s Computable. Let’s start by computing various kinds of natural numbers.

Let’s say the input will encode numbers of as a sequence of "X" terminated by at least one "O".

For example,

• Zero is a tape with ["O"].
• One is a tape with ["X", "O"].

First, consider creating a machine to do a simple “add 1” operation.

Add 1 Machine

1. If symbol is ["O"]: don’t move, write ["X"], change to state 2.

   If symbol is ["X"]: move to the next cell, stay in state 1.

2. For all symbols, move to the next cell, write “O”, change to state 3.

3. For all symbols, halt.

Second, consider creating a machine to do a simple “subtract 1” operation.

Subtract 1 Machine

1. If symbol is ["O"]: Move to the previous cell, switch to state 2. Note that if the tape has zero, this will fall of the front of the tape, breaking the machine.

   If symbol is ["X"]: move to the next cell, stay in state 1.

2. For all symbols, write ["O"], change to state 3.

3. For all symbols, halt.

We can see that with an “add 1” machine and a “subtract 1” machine, we can do a great deal of mathematics on natural numbers.

Add Two Numbers. Consider a machine that will add two numbers. We’d start with a tape that encoded two numbers, for example ["X", "X", "O", "X", "X", "X", "O"].

This machine would terminate with a sum with some extra "O" symbols. A result like ["O", "O", "O", "X", "X", "X", "X", "X", "O"] would be expected.

We can implement this by combining our “add 1” and “subtract 1” machines. We need to an “add 1” to the right-hand number and a “subtract 1” on the left-hand number until the left-hand number vanishes in a flurry of "O" symbols.

Subtract Two Numbers. We can also subtract two numbers. We’d start with a tape that encoded two numbers, for example ["X", "X", "O", "X", "X", "X", "O"].

This machine would do “subtract 1” from each number until one of them has been reduced to zero. Depending on the locations of the "O" symbols we have a positive or negative result.

Yet More Math. Multiplication is repeated addition. Given two numbers, call them, l and r, we’d do this via (1) copy r to the end of the tape and (2) subtract 1 from l until r was reduced to zero.

You can also think of this machine a having three numbers on the tape: l and r and p. The machine would start by creating an extra "O" at the end of the tape to, effectively set p to zero. Then the cycle is “add r to p” and “subtract 1 from l”, both of which we’ve already implemented.

Division, similarly, is repeated subtraction. Given two numbers, call them, l and r, create a third number, q at the end of the tape. To divide l and r, subtract r from l and add 1 to q. This is repeated until l is less than r.

Note that “comparison” is easily done via subtraction. However, the subtraction defined above is “destructive”, in that it updates both numbers. One way to handle this is to make a complete copy of l and r for comparison purposes.

Optimization. Note that these naive repeated additional or repeated subtraction algorithms are inefficient. The point is to define what’s computable in principle. Once we know what’s computable, we can work at optimization later.

Exercise 2

1. Build the “add 1” and “subtract 1” machines.

2. Build a “test driver” program. This will exerise a given machine with particular inputs and check the outputs.

   You’ll need a function to create an input tape from a simple tuple. A tuple like (2, 3) should create a tape of ["X", "X", "O", "X", "X", "X", "O"].

   You’ll need a function to summarize the resulting tape into a simple tuple. A tape like ["X", "X", "X", "O", "X", "X", "O"] should produce the tuple (2, 3).

   You can then define a machine, and an input tape. The resulting tape can be easily checked for the right answer.

Once we have the test driver, we can explore some alternate implementations. We can also explore some alternate definitions of Turing Machine processing rules.

Better Implementations

The initial implementation (using various kinds of strings and integers) suffers from a number of problems. We can (and will) use the State design pattern to fundamentally restructure the definition of a machine.

Machine. A Machine is a class definition that includes several attributes and methods.

• The Tape. The tape on which the Machine is currently working. This object can be responisble for tape’s current position, plus the next and previous movements. Additionally, this class can handle growing the tape so that the next operation always works.
• The collection of states. Each state is an instance of the State class. Each State object is a collection of Rule objects.
• The current State. This is a variable that contains the machine’s current state.
• Machine.next(), Machine.prev() methods to update the position of the tape.
• Machine.write() method to change the symbol on the tape.
• A Machine.run() method that accepts a tape, a state collection, and an identifier for a starting state. It steps through the machine’s operating cycle with the given tape, printing a log of the tape at each step.

State. A State is a class definition that includes a rule for each symbol. We used a simple dictionary in the first implementation. A subclass of dictionary will be fine. We don’t need to extend it, so we can have something like

class State( dict ):
    pass

State Change. We can use the Command design pattern to define some reusable command objects. We’ll need a bunch of Command classes and instances. Each StateChange object is given a particular machine to update.

We can define an abstract super class called StateChange. Each specific state change is a polymorphic subclass to make specific changes to the Machine’s Tape.

• Write. A StateChange subclass with a Next.__call__( self, machine )() method which calls machine.write(self.symbol).
• No_Write. A StateChange subclass with a Next.__call__( self, machine )() method which does nothing.
• Next. A StateChange subclass with a Next.__call__( self, machine )() method which updates the machine by calling machine.next().
• Prev. A StateChange subclass with a Next.__call__( self, machine )() method which updates the machine by calling machine.prev().
• Stay. A StateChange subclass with a Next.__call__( self, machine )() method which does nothing.

Rule. Each Rule has several parts that we initially encoded as strings. Given these Command class definitions above, we can create a bunch of individual objects that slightly simplify our machine definition.

write_X = Write("X")
write_O = Write("O")
nothing = No_Write()
next = Next()
prev = Prev()
stay = Stay()
halt = None

Now we can create Rule objects using these objects instead of string literals. Instead of checking the rule’s attributes for string values, we can directly invoke the rule’s attributes, since they’re callable objects.

A rule would now look like this.

rule_1_map = {
    'X': Rule(nothing, next, 0),
    'O': Rule(nothing, next, 1),
    None: Rule(write_x, next, halt) }

In our machine, we can then revise how we evaluate the rules. Instead something like this:

if rule.move == "next": machine.next()
elif rule.move == "next": machine.next()
else:
    assert rule.move is None
if rule.write is not None:
    machine.write( rule.write )

We can do the following:

rule.move( machine )
rule.write( machine )

Eliminating the if statements will result in a net speedup as well as a simplification.

Tape. The Tape class has define the tape as a list. It can also implement the next and previous, including a feature to extend the tape as necessary. This class can handle current position of the tape, also.

Exercise 3

1. Define the required classes for an object-based Turing Machine implementation.

   • Machine
   • State
   • StateChange
   • Rule
   • Tape

2. Define a function that implements this new Turing Machine.

   turing_obj(transitions, tape)

   Accepts a dictionary of transition rules built using objects instead of strings and an input tape. Starts in rule 0 with tape at position 0. Executes the various transitions until the machine reaches a transition where the next state is None, then it halts.

   Prints a log showing the tape as it moves and changes.

3. Using your existing test driver from Exercise 2, assure yourself that the new machine works as well as the old machine.

Consequences

As we noted above, the set of real numbers is uncountably infinite. However, this Turing Machine definition of numbers can be shown to be countably infinite. This means that there are some real numbers which cannot be computed.

In spite of this gap between the two orders of infinity, there are enough real numbers that can be computed that it’s fairly difficult to define the kinds of numbers which are not computable. Also, the set of computable numbers is closed under ordinary arithmetic operations: given two computable numbers the sum, difference, product or quotient are also computable.

What’s more important is that our two implementations of Turing Machines prove that Python can easily work with all computable numbers. Consequently, the Python language (like all other programming languages) is “Turing Complete” and suitable for use doing anything that involves numbers.

Since we can encode almost anything as a number, we can create Python programs to process this domain of “almost anything”. There are – at the fringes of mathematics – some things which cannot be encoded as numbers. That’s way beyond the scope of this book. If you’re interested, though, you can research the “Halting Problem”, “Chaitin’s Constant” and “The Busy Beaver Problem” for some things which are clearly not computable and things which may not be computable.

Other Applications

Some simple variations on the basic Turing Machine act as a pattern recognizers. These Finite State Machines are the typical solution to a large number of problems.

As an example, consider a machine to recognize simple dates in the form mm/dd/yyyy. We’ll tolerate a single digit month or a single digit day. But we must have all four digits for the year.

Clearly, we’ll have to expand our set of symbols to include all Unicode characters. Also, it’s simpler if we work with “character classes” (i.e., digits) instead of patiently listing each symbol.

We can – if necessary – prove that a list of symbols is equivalent to a single symbol by patiently building the equivalent Turing Machine. The individual rule is simply repeated for each symbol in the class.

Also, we’re not so much interested in processing a vague, general “Tape”. We’re interested in processing a specific string. However, a string – for our purposes – is a sequence and therefore is almost equivalent to a list.

Finally, we’re never going to write. It’s a read-only tape of symbols.

Instead of writing, we’re going to holt in one of two states: an accepting state or a rejecting state. If we halt in an accepting state, the string of characters matched the desired pattern.

Short-Hand. We’ll use a short-hand to define the Turing Machine that matches the above string. We’ll just write the symbol, and the next state like this: digit: 1. We’ll assume that we always move to next position on the input tape.

Further, for all other characters, not given explicitly in the rules, the machine simply halts in a “rejecting” state.

Pattern Matcher

0. digit: 1.
1. digit: 2. “/”: 3.
2. “/”: 3.
3. digit: 4.
4. digit: 5. “/”: 6.
5. “/”: 6.
6. digit: 7.
7. digit: 8.
8. digit: 9.
9. digit: 10.
10. At this point, we’re at the end of the input string. We can halt, accepting the string as matching the pattern.

Building the Machine. One can see that the state transitions in this kind of simple pattern-matching machine are so simple that a short-hand notation could be used.

For example: "\d\d?/\d\d?/\d\d\d\d" would describe the pattern. In this case, "\d" stands for “match a digit and advance to the next state”. And "\d?" stands for “match a digit and advance to the next state or look ahead to the next character and advance to the next state if it will match.”

Refer back to the section on Complex Strings: the re Module. In essence, a regular expression pattern defines a kind of finishte-state machine to match the given string as if it was a specialized one-way tape.

Alternative Specifications

There are number of alternative formulations for the Turing Machine.

Two-way infinite tapes. Above, we assumed that the tape had an end and went infinitely far to the right. This has a nice parallel with the Python list structure. When the transition rule attempted a “next” at the end of the tape, we simply appended a new, empty cell to the list.

We can change this to allow the tape to stretch infinitely far to right or the left. To allow the tape to go infinitely far to the left, we have several choices:

• Continue to model the the tape as a dict. However, when we attempt to go to the previous cell from position 0, we need to insert a new, empty cell at position 0 and leave the position number alone.
• Model the tape as a dict and use dict.setdefault() to be sure that a new position has a proper empty cell before processing.

This is a little bit like creating a tape with a bunch of empty cells before and after the relevant data for the problem at hand.

Two-dimensional tapes. Instead of using a one-dimensional infinite tape, we could consider a two-dimensional magnetic “surface”, which can be moved left, right, up and down.

This changes our “tape” dramatically. Rather than a simple list, we should probably use a dict with a two-tuple as the key. Our initial state would be at position (0,0) on the surface.

Our movement rules, would look something like this.

class Right( StateChange ):
    def __call__( self, machine ):
        x, y = machine.position
        machine.position = x+1, y

class Left( StateChange ):
    def __call__( self, machine ):
        x, y = machine.position
        machine.position = x-1, y

The contents of the surface, then, would be available as surface.setdefault( position, None ). This would return any value that was on the surface, and create an empty cell if necessary.

Multi-Step movement of the head. Above, we simplified the tape movements to be one-step. Either previous and next, or up, down, left and right. We can also change the definition to permit multiple-step movements instead of single-step movements.

This would extend our basic state change class definitions to accept a parameter with the distance to move.

In most cases, there isn’t an easy way to make use of this extension. Most of the processing we can imagine requires stepping over each symbol one at time. We might, however, slightly simpliify some pattern recognition with multiple-position skips.

Multiple tapes. An interesting extension is to add a second tape. In this case, we have two input symbols and two sets of transitions. Either tape can be moved and either tape can write a new symbol.

You might use one tape for input and one tape for the results. In this case, and “Add 1” operation would copy all the input symbols to the output tape, and then write one extra symbol to the output tape.

Arbitrary Alphabet. As we noted in Other Applications, it’s sensible to allow a much larger alphabet than just two symbols.

Simpler State Changes. We defined our machine to do both a tape movement and a write. We specified that the tape movement could be next, previous or none. We also said that there could be an optional write of a new symbol.

This can be broken down into finer steps. We can, for example, separate the moving and the writing and say that a rule has the following attributes:

• A current symbol on the tape to match.
• A change: either move the tape, or write.
• Next State.

This would create additional states in some machines because we would have to separate writing from moving the tape.

Exercise 4

Pick one of these alternate formalation for the Turing Machine.

• Two-way infinite tapes.
• Two-dimensional tapes.
• Multi-Step movement of the head.
• Multiple tapes.
• Simpler State Changes.

1. Implement a new Turing Machine with this alternate formulation.
2. Revise your test cases from Exercise 2 to fit your new machine formulation.
3. Create an additional test simply to exercise each feature of your new machine.

There is an important question raised by the alternative formulations of the Turing Machine. Do these alternatives allow more computable numbers?

It turns out we can find a way to build any of these machines using any other machine. They are all provably identical.