Turing's Thesis: Computability and Algorithms

Turing's Thesis and the Problem of Computability

Thesis 1

"Every problem that can be solved algorithmically can be solved by a Turing machine."

Concepts Associated with Thesis 1

• Algorithm: A set of rules that can be mechanically applied to solve a problem of a given class. Mainly used in mathematical contexts.
• Calculation: Any transaction which is carried out by manipulation of symbols as a means of representation. The symbolic operations are atomic, that is, quite simple, and are held in a computer. The action of the computer will depend on the symbols that have the system and the internal state in which the computer is.

Thesis 2

"Every computable function can be computed by a Turing machine. Every problem that can be solved by algorithmic methods can be solved by a Turing machine."

Concepts Associated with Thesis 2

• Computable Function: Classes of problems that can be solved algorithmically, that is, if the algorithm is given the corresponding arguments, then those values are computed, completing the task in a finite number of steps.

Thesis 2

"Every computable function can be computed by a Turing machine. Every problem that can be solved by algorithmic methods can be solved by a Turing machine."

Concepts Associated with Thesis 2

• Computable Function: Classes of problems that can be solved algorithmically, that is, if the algorithm is given the corresponding arguments, then those values are computed, completing the task in a finite number of steps.

Turing's Thesis 2 was fundamental to both the development of Cognitive Psychology and the subsequent development of Artificial Intelligence. What follows from argument 2 is that if you could provide a description in terms of a computable function of any psychological state, there would be a Turing machine that could compute it. For example, if you could give a definition - algorithmic-computational - of processes such as memory, reasoning, having a belief system, or even more complex cognitive processes, then we could have computer models as described by Turing machines capable of reproducing them. The consequences in the field of Artificial Intelligence would be evident; we could build artificial agents in terms of subject-Lowe, implementing computer systems as described so that they could implement cognitive processes we call superior.