Métodos computacionales

Computability Theory

Contents

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:

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.

The main problem with Turing machines is that a different one must be constructed for every new computation to be performed [3]. 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.

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 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.

American linguist Noam Chomsky defined in 1956 a classification of languages in terms of four levels of complexity. This four-level hierarchy, called the Chomsky hierarchy, corresponds to four classes of machines [4].

The following table summarizes each of Chomsky's four types of grammars, the class of language it generates, and the type of machine that recognizes it.

Grammar Language Machine
Type 0
Unrestricted
grammar
\(L_{\texttt{RE}}\)
Recursively enumerable language
Turing machine (TM)
Type 1
Context-sensitive
grammar
\(L_{\texttt{CS}}\)
Context-sensitive language
Linear-bounded automaton (LBA)
Type 2
Context-free
grammar
\(L_{\texttt{CF}}\)
Context-free language
Pushdown automaton (PDA)
Type 3
Regular
grammar
\(L_{\texttt{Reg}}\)
Regular language
Finite automaton (DFA/NFA)

Each language of type \(i\) (where \(i \ge 1\)) is a proper subset of the family of type \(i − 1\). The following diagram exhibits the relationship clearly: