(Halting Problem) |
|||
| Line 1: | Line 1: | ||
| + | [[Category:MA453Spring2009Walther]] | ||
| + | |||
One of my favorite theorems to date is Turing's Halting Theorem, better known as the Halting Problem. It is one of the first theorems shown to be uncomputable by any deterministic finite automata. The problem is this: | One of my favorite theorems to date is Turing's Halting Theorem, better known as the Halting Problem. It is one of the first theorems shown to be uncomputable by any deterministic finite automata. The problem is this: | ||
Latest revision as of 16:39, 21 January 2009
One of my favorite theorems to date is Turing's Halting Theorem, better known as the Halting Problem. It is one of the first theorems shown to be uncomputable by any deterministic finite automata. The problem is this:
Given a Turing-class machine, a program, and an input of finite length, is it possible for said machine to determine if the input will result in the program running to completion (halting) or if the input will result in an infinite loop.
It operates in some sense as an extension to the incompleteness theorem -- Not only are there functions whose output we cannot compute, but it is impossible to differentiate those problems from the problems that are really difficult.
The implications of this are staggering. If human consciousness is nothing but a computing machine (an admittedly elaborate one at that) then there is a foundational limit to the human mind's ability to understand and find solutions.
