Church Turing Thesis

The Church-Turing Thesis for Decision Problem""s

There is an effective procedure to solve a decision problem if, and only if, there is a Turing Machine that halts for all input strings and solves the problem.

The extended Church-Turing thesis for Decision Problem""s

A decision problem P is partially solvable if, and only if, there is a Turing Machine that accepts precisely the elements of P whose answer is yes.

Basically, this means that any Decision Problem that can be solved is computable. In other words, any problem that can be solved in the real world can be solved on a Turing Machine.

--Gordon Worley

See also Singularity Questions/AGIq16.