Métodos computacionales

Turing Machines

General Overview

A Turing machine (TM) is a hypothetical machine (computing device) first conceived by the English mathematician Alan Turing in 1936 to help solve a specific question in mathematical logic. Despite its simplicity, the machine can simulate any computer algorithm, no matter how complicated it may be.

We may visualize a TM as follows [3]:

The machine consists of a finite control (equivalent to a CPU in modern day computers), which can be in any of a finite set of states. There is a tape divided into squares or cells ; each cell can hold any one of a finite number of symbols.

Initially the input, which is a finite-length string of symbols chosen from the input alphabet, is placed on the tape. All other tape cells, extending infinitely to the left and right, hold a special symbol called the blank. The blank is a tape symbol but not an input symbol.

There is a tape head that is always positioned at one of the tape cells. The TM is said to be scanning that cell. Initially the tape head is at the leftmost cell that holds the input.

A move of the TM is a function of the state of the finite control and the tape symbol scanned. In one move the TM will:

  1. Change state. The next state optionally may be the same as the current state.

  2. Write a tape symbol in the cell scanned. This tape symbol replaces whatever symbol was in that cell. Optionally, the symbol written may be the same as the symbol currently there.

  3. Move the tape head left or right.

Formally, a TM is defined by the 7-tuple \(M = (Q, \Sigma, \Gamma, \delta, q_0, B, F) \), where:

Let \(M\) be a TM and \(w\) a string.

TM Example

Let’s define a TM that accepts the language \(\{ a^n \; | \; n \ge 0, n \bmod 2 = 0\}\). In other words, the TM should accept strings that contain a sequence with an even number of \(a\)’s.

The formal specification of this Turing machine \(M\) is:

$$ M = (\{q_0, q_1, q_2 \}, \{ a \}\, \{ B, a \}, \delta, q_0, B, \{ q_2\} ) $$

where \(\delta\) is given by the following table:

State Symbol
\(a\) \(B\)
\(q_0\) \((q_1, a, R)\) \((q_2, B, L)\)
\(q_1\) \((q_0, a, R)\)
\(q_2\)

We can alternatively represent \(\delta\) using a state diagram as shown below [3]:

The diagram consists a set of nodes corresponding to the states of the TM. An arc from state \(q\) to state \(p\) is labeled by one or more items of the form \(X/Y;D\), where \(X\) and \(Y\) are tape symbols, and \(D\) is a direction, either \(L\) or \(R\). That is, whenever  \(\delta(q,X) = (p, Y, D)\), we find the label \(X/Y;D\) on the arc from \(q\) to \(p\). Also, in the above diagram the blank symbol \(B\) is represented with an underscore (_).

Additional Terminology

Decidable and Recognizable Languages

Let \(M\) be a TM and \(L\) a language \((L \subseteq \Sigma^∗\)) [2].

NOTE: The term “recursive” used above is not limited to the idea of recursive functions as considered in programming (a function that calls itself). In the early days any computation was viewed as a “recursion”.

Also note that:

Undecidable Problems

An undecidable problem is a decision problem (a problem that can be posed as a yes–no question) for which it is proved to be impossible to construct an algorithm that always leads to a correct yes-or-no answer [6]. The halting problem is an example: it can be proven that there is no algorithm that correctly determines whether arbitrary programs eventually halt when run. See also a list of some known undecidable problems.

Universal Turing Machine

The main problem with Turing machines is that a different one must be constructed for every new computation to be performed [4]. This is why Alan Turing proposed a much more general computing device which was later known as a universal Turing machine (UTM).

Along with the input on the tape, the UTM also takes in the description of a machine \(M\). The UTM can go on then to simulate \(M\) on the rest of the contents of the input tape. A UTM can thus simulate any other machine. This principle is considered to be the origin of the idea of a stored-program computer by John von Neumann in 1946 that now bears his name: the von Neumann architecture.

Church-Turing Thesis

The Church-Turing thesis (named after American mathematician Alonzo Church and Alan Turing) establishes that any real-world computation can be translated into an equivalent computation involving a Turing machine [5]. There has never been a proof, but the evidence for its validity comes from the fact that every realistic model of computation, yet discovered, has been shown to be equivalent.

For different tasks some computational models are more efficient than others in terms of time and memory. Yet, there exist questions (undecidable problems) which an ordinary computer cannot answer, and according to the Church-Turing thesis, no other computational device can answer such a question.

Turing Completeness

Turing completeness is a classification for a system of rules that manipulate data [1]. For instance, programming languages and CPU instruction sets are examples of formal rule systems that access and modify data. If the rules can simulate a TM, the rules are said to be Turing-complete or computationally universal. No physical system can have infinite memory, but if the limitation of finite memory is ignored, most programming languages are otherwise Turing-complete. A Turing-complete system can be proven mathematically to be capable of performing any possible calculation or computer program.

Programming languages like Java, C++, C, Rust, Go, Python and others are Turing-complete. Data languages like HTML, XML, JSON and Markdown are always non-Turing-complete as they are designed to represent data and not computation.

To show that something is Turing-complete, it is enough to show that it can be used to simulate some Turing-complete system. For example, an imperative language is Turing-complete if it has conditional branching (“if” and/or “while” statements) and the ability to read and write an arbitrary amount of data items in memory.

References