Church's Thesis: Definition and Proof

  • Context: Graduate 
  • Thread starter Thread starter Agaton
  • Start date Start date
  • Tags Tags
    Thesis
Click For Summary
SUMMARY

Church's Thesis asserts that every effectively computable function is recursively computable, meaning any function that can be executed by an algorithm is computable by a Turing machine. This statement is often regarded as a conjecture or hypothesis rather than a formally provable theorem. It is equivalent to Turing's Thesis concerning the capabilities of Turing machines. The discussion highlights the foundational nature of Church's Thesis in the realm of computability theory.

PREREQUISITES
  • Understanding of computability theory
  • Familiarity with Turing machines
  • Basic knowledge of recursive functions
  • Concept of algorithmic processes
NEXT STEPS
  • Research the implications of Turing's Thesis in computability
  • Study the differences between recursive and non-recursive functions
  • Explore formal proofs related to computability theory
  • Investigate the historical context and development of Church's Thesis
USEFUL FOR

Mathematicians, computer scientists, and students of theoretical computer science interested in the foundations of computability and algorithmic processes.

Agaton
Messages
26
Reaction score
0
Church's thesis says that 'every effectively computable function is recursively computable'.

The meaning of the statement is clear enough. In more simpler words, it says that every function that have an algorithm is computable by Turing machine.

My question is that what is this statement and where does it come form? I mean, is that a mathematical statement? Is there any 'mathematical proof' for that?

Thanks
 
Physics news on Phys.org
It has the status of a conjecture or hypothesis. Apparently it cannot be proven formally. It has been shown to be equivalent to Turing's Thesis re the Turing Machine.

It seems it could also be regarded as a definition of a computable function, but I'll let others comment on that.
 
Last edited:

Similar threads

Undergrad Faulty definition of r.e. set in Wiki?
  • · Replies 8 ·
Replies
8
Views
2K
Graduate Questions concerning the Church-Turing thesis
  • · Replies 3 ·
Replies
3
Views
2K
Undergrad Church-Turing-Deutsch principle and Incompleteness-Halting.
  • · Replies 5 ·
Replies
5
Views
2K
Undergrad Proof that BB(k) grows faster than any computable function
  • · Replies 15 ·
Replies
15
Views
7K
Is Alan Turing given too much credit when it comes to computers?
  • · Replies 29 ·
Replies
29
Views
5K
MHB Can Turing Machine Decidability Extend to Complex Algorithm Outputs?
  • · Replies 1 ·
Replies
1
Views
2K
Graduate Concrete examples of randomness in math vs. probability theory
  • · Replies 11 ·
Replies
11
Views
3K
Undergrad Proving The Church-Turing-Deutsch Principle
  • · Replies 39 ·
2
Replies
39
Views
7K
Is computation synonymous with functions in computer science?
  • · Replies 41 ·
2
Replies
41
Views
5K
Undergrad Recursive Ordinals and Creativity
  • · Replies 4 ·
Replies
4
Views
2K