Turing Machine

What does the Church-Turing Thesis postulate?

Salinas Molina, M. A. (2011), proposes that the Church-Turing thesis defines the computability of a computable function, an important result in computer science because it helped to formulate a discipline of human knowledge: Computer science.

His real success was to bring out the compiler theory, whose object is to make the programs that run on computers closely related to the concepts of algorithm and recursion, its statement is presented as follows: A function is effectively computable if only if it is Turing computable. This includes two concepts, the first on the effectively computable function that refers to the recursive functions that are an effective computation, stated by Church in the lambda calculus; the second on the effective procedure, definition given by Turing in the sense of successfully executing a sequence of instructions in a Turing machine.

Vargas, C., & de Costa Rica, I. T. (1996), establishes that the Church-Turing thesis deals with the algorithm for the calculation of a mathematical function, which is impossible to demonstrate mathematically, since the concept is of an intuitive nature. In this sense, we can establish that the computable coincides with the Turing-Computable (computable by means of MT).

What is the difference between a search problem and a decision problem?

When we talk about a search problem, the Turing Machine understands that it receives an input of information and returns an output depending on what is supplied, on the other hand, when the MT is confronted with a decision problem, where the input data can be a value from 1 to 'n' values, the expected results would be presented in a binary form, that is, ones and zeros, understanding that its output would be a value between 'True' or 'False', Martínez, G. D. J. R. (2016).

Why in the case of decision problems, can we refer interchangeably to problems and languages?

The execution process of a Turing Machine, starts initially from a tape that forms a Tuple of values, which are represented, as a language of sets of strings, Favio Perea (2013).

For example: we can represent the execution of values in a TM, by means of the following set of strings

T = (Σ, Q, q0, qf, δ)

Where:

Σ = ∅ is a finite alphabet containing a distinguished symbol, called the white symbol,

Q = ∅ is the finite set of states, which includes q0 and qf, q0 is the initial state,

qf is the final state of acceptance

δ is a transition function whose domain is a subset of Q × Σ and whose contradomain is Q × Σ × M. Such that if δ is defined for the pair (l, s) ∈ Q × Σ and δ (l, s) = (l', s', m).

Then:

(l) is the current state,

(s) the symbol being read by the head, 

(l') the state to which the transition will take us (s') the symbol to be written,

(m) the movement that the head will make.

Bibliography

• Salinas Molina, M. A. (2011). Computability and Turing machine.
• Muro, V. (2018, January). Computability, randomness and the Church-Turing Physics Thesis. I Jornadas de Estudiantes del Departamento de Filosofía.
• Vargas, C., & de Costa Rica, I. T. (1996). Artificial Intelligence (AI) and Cognitive Science be known and discussed in. Memoria, 348.
• Martínez, G. D. J. J. R. (2016). Some challenges to the Turing test. Luxiérnaga-Philosophy Student Journal, 6(11), 21-21.