9.2.1.1. A General Model of Computation¶

We would like to define a general model of computation that is as simple as possible. The reason is that we want to be able to understand the limits of what is possible in computing, but that is rather hard to do with a complicated definition for a "computer" is. But then, we need to be confident that whatever model we do pick, that it actually represents all of the fundamental capabilities of a "computer".

"State machines" are simple to understand. There are a number of different state machines, with a range of capabilities. We will discuss a particular one, called a Turing machine. As we define "capability", the key is ability, not efficiency.

The necessary capabilites for any such "machine" are these:

• Read
• Write
• Compute

A Turing machine is defined as follows. It has a one-dimensional tape, divided into squares. This tape extends infinitely to the left and to the right. Each square can store one character. The machine has a single I/O head that at any instant in time is "on" one of the squares. The control unit of the machine is defined by a set of abstract states. At any given instant, the machine is said to be "in" one of the states, and has a set of actions that can be performed when in that state. From the current state, the machine will read the symbol on the current square, and will then do the following (depending on the value of the symbol that it sees):

• Overwrite that symbol with a new symbol,
• Move the tape head either left (\(L\)), right (\(R\)), or stay (\(S\))

The letters that can appear on the tape are an important part of the definition for a given Turing machine. The alphabet of the machine is these letters that may appear in the input. In addition to the letters of the alphabet that can define an input string, there is also the blank character. When talking about strings, since a blank is hard to see, we will use the \(\#\) character to represent a blank character. Note that including \(\#\) in the alphabet is for convenience only. We want to be able to read our specifications without being confused.

The input to the machine is the intial contents of the tape, which is described by listing all of the tape squares from the leftmost non-blank tape cell to the rightmost non-blank tape cell. Naturally, there must be a finite number of non-blank symbols on the tape. And the input string might have some blank squares in between the non-blank squares that define the input.

Now, we know that at any instant the machine is in some state, and that the input head is under some square on the tape. The machine reads the symbol, and responds by going to some state (possibly the current state, possibly another state), writing some letter onto the square (possibly the same letter as is currently in the square, possibly another), and then moving the head either one square left, one square right, or leaving the head in the current square. That is everything that the machine can do.

A Turing machine is formally defined as (\(Q\), \(\Sigma\), \(\Gamma\), $s$, \(F\), \(\delta\)) where

• \(Q\) is a finite set of states.
• \(\Sigma\) is an alphabet. This is used to define the input.
• \(\Gamma\) is another alphabet that at least includes \(\Sigma\) and \(\#\). It might include other symbols, and is the alphabet used by the computational process.
• \(s \in Q\) is the initial state.
• \(F \subset Q\) is the set of final states.
• \(\delta\) is a partial function from \(Q \times \Gamma\) to \(Q \times \Gamma \times \{L, R, S\})\).

The machine operates as follows: For \(q \in Q\), \(a \in \Sigma\) and \(\delta(q, a) = (p, b, m)\), when in state \(q\) and scanning \(a\), enter state \(p\), replace \(a\) with \(b\), and move the head (\(m\) is \(L\), \(R\), or \(S\)).

To do computation, we have to have some conventions about starting and ending the process. The machine stops immediately if (1) it enters any final state, or (2) it is in a state and scans a character for which there is no transition. (Note that there are many ways to define Turing Machines, and some definitions require an explicit reject state. We do not.)

We can also describe a Turing Machine as a graph, whose nodes are the states in \(Q\) and with edges corresponding to the transitions in \(\delta\). Further, we can visualize the processing of the machine as the movement of a head across the tape.

Settings

Saving...
Server Error
Resubmit

Turing Machines can accept Regular Languages and Context-Free Languages. In the following example, we have a TM that accepts \(L(a^*b^*c^*)\).

9.2.1.2. Interpreting Turing Machines¶

A configuration for a Turing machine looks like this:

This means that the TM is on state \(q\), the tape contains \(aaba\#\underline{\#}a\) and read / write head position is on the underlined \(a\). In this book, any TM starts running with the read/write head position is on the first Tape letter from the left.

A halted configuration occurs when the machine do not find a move from the given state using the tape letter (the current configuration). In other words, TM halts if there is no \(\Delta\) defined. That is why in this book we always assume that there are no transitions defined out of the final state. Therefore, any TM will halt once it entered a final state.

A computation is a sequence of configurations for some length \(n \geq 0\).

\(M\) is said to halt on input :math:`w` iff \((s, w\underline{\#})\) yields some halted configuration.

\(M\) is said to hang on input :math:`w` if \((s, w\underline{\#})\) yields some hanging configuration. That means go into an infinite loop.

9.2.1.3. Turing Acceptors and Trurng Transducers¶

Turing machines compute functions from strings to strings. Formally: Let \(f\) be a function from \(\Sigma^*_0\) to \(\Sigma^*_1\). Turing machine \(M\) is said to compute \(f\) when, for any \(w \in \Sigma^*_0\), if \(f(w) = u\) then

Such a function \(f\) is said to be a Turing-computable function.

Here is how we express multiple parameters: For \(f(w_1, ..., w_k) = u\),

One way to express functions on natural numbers is to represent a number using unary notation. (Remember, we are not concerned about is efficient, we are concerned about what is possible.) In this case, we represent the value 0 as an empty string. We say that \(f: \mathbb{N} \rightarrow \mathbb{N}\) is computed by \(M\) if \(M\) computes \(f': \{I\}^* \rightarrow \{I\}^*\) where \(f'(I^n) = I^{f(n)}\) for each \(n \in \mathbb{N}\).

9.2.1.4. Turing-Decideable vs. Turing-Acceptable Languages¶

A language \(L \subset \Sigma_0^*\) is Turing-decidable iff function \(\chi_L: \Sigma^*_0 \rightarrow \{\fbox{Y}, \fbox{N}\}\) is Turing-computable, where for each \(w \in \Sigma^*_0\),

Example: Let \(\Sigma_0 = \{a\}\), and let \(L = \{w \in \Sigma^*_0: |w|\ \mbox{is even}\}\).

\(M\) erases the marks from right to left, with current parity encode by state. Once blank at left is reached, mark \(\fbox{Y}\) or \(\fbox{N}\) as appropriate.

There are many views of computation. One is functions mapping input to output (\(N \rightarrow N\), or strings to strings, for examples). Another is deciding if a string is in a language.

\(M\) accepts a string \(w\) if \(M\) halts on input \(w\).

• \(M\) accepts a language iff :math:M` halts on \(w\) iff \(w \in L\).
• A language is \(Turing-acceptable\) if there is some Turing machine that accepts it.

Example: \(\Sigma_0 = \{a, b\}\), \(L = \{w \in \Sigma^*_0: w\ \mbox{contains at least one}\ a\}\).

Is this language Turing decidable? Of course. Instead of just running left, invoke another state that means "seen an \(a\)", and print \(\fbox{Y}\) if we reach \(\#\) in that state, \(\fbox{N}\) otherwise.

Every Turing-decidable language is Turing-acceptable, because if the machine would have printed \(\fbox{Y}\), then the machine can halt instead, or if the machine would have printed \(\fbox{N}\), then it can hang left.

Is every Turing-acceptible language Turing decidable? This is the Halting Problem.

Of course, if the Turing-acceptible language would halt, we write \(\fbox{Y}\). But if the Turing-acceptible language would hang, can we always replace it with logic to write \(\fbox{N}\) instead? Example: Collatz function.

9.2.1.5. Making More Complicated Machines¶

Lemma: If

for string \(w\) and

then

Insight: Since \((q_2, w_2\underline{a_2}u_2) \vdash^*_M (q_3, w_3\underline{a_3}u_3)\), this computation must take place without moving the head left of \(w_2\) The machine cannot "sense" the left end of the tape. (And if it had moved left, it would have hung.) Thus, the head won't move left of \(w_2\) even if it is not at the left end of the tape.

This means that Turing machine computations can be combined into larger machines:

• \(M_2\) prepares string as input to \(M_1\).
• \(M_2\) passes control to \(M_1\) with I/O head at end of input.
• \(M_2\) retrieves control when \(M_1\) has completed.

Here are some basic machines and notation

• \(|\Sigma|\) symbol-writing machines (one for each symbol): Any give letter \(\sigma\) has a symbol-writing machine named \(\sigma\).
• Head-moving machines, named \(R\) and \(L\), move the head appropriately.
• Start state indicated with \(>\).
• Transitions on anything other than (for example) \(\#\) are labeled \(\overline{\#}\)
• Multiple copies of a machine get a superscript: \(R^2\) means move right twice.

9.2.1.6. Turing Machine Extensions¶

When we give extentions or new functionality to a computing system, sometimes they change something fundamental about the capabilies of the system. For example, when we add non-determinism to an algorithm, we might change the cost of the underlying problem from exponential to polynomial time. But, other changes do nothing fundamental. In terms of Turing machines, our concern is what the machine can do, rather than how long it takes to do it. Does non-determinism help us to solve the Halting problem? No. Likewise, the following extensions do not increase the power of Turing Machines.

• Provide a two-way infinite tape

  This does not give Turing machines new capability. To make this clear, we can simulate the behavior of a two-way infinite tape using a standard one-way infinite tape. Just bend infinite tape in the middle, and store both directions of the tape into a single cell. This requires a greatly expanded alphabet, because we now need to be able to represent any combination of two characters. This will need more states, and probably more time. But it does not allow anything new in terms of capability.

• Multiple tapes (each with its own head)

  Again, we can simulate this with encoding multiple symbols into a single table cell. For example, to simulate two tapes (each with a head), we encode in each cell the corresponding two symbols, and a two binary markers to indicate if the tape head is currently in the corresponding cell of the two tapes.

• Multiple heads on one tape

  This is easier than encoding multiple tapes. We merely encode the heads onto the tape, and simulate moving them around.

• A two-dimensional tape

  All that we need to do is find a mapping from 2D to 1D, which is fairly easy. One approach is to work in diagonals, in the order (0, 0), (0, 1), (1, 0), (0, 2), (1, 1), (2, 0), and so on.

• Non-determinism

  We can simulate nondeterministic behavior in sequence, doing all length 1 computations, then length 2, etc., until we reach a halt state for one of the non-deteriministic choices. So we see that while non-determinism can save a lot of time, it does not change what can (eventually) be done.