Church's Thesis: Definition and Proof

  • Thread starter Agaton
  • Start date
  • Tags
    Thesis
In summary, Church's thesis, also known as the Church-Turing thesis, states that every effectively computable function can be computed by a Turing machine. This statement carries the status of a conjecture and cannot be formally proven. It has been shown to be equivalent to Turing's Thesis on the Turing Machine. It can also be seen as a definition of a computable function.
  • #1
Agaton
26
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
  • #2
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:

FAQ: Church's Thesis: Definition and Proof

What is Church's Thesis?

Church's Thesis, also known as the Church-Turing Thesis, states that any effectively computable function can be computed by a Turing machine. It is a hypothesis in the field of computer science and mathematics, and is widely accepted as a fundamental principle of computation.

What is the proof behind Church's Thesis?

The proof of Church's Thesis is based on the concept of equivalence between different models of computation. It is based on the idea that any algorithm or program can be represented as a Turing machine, and therefore, any computation that can be performed by a Turing machine can also be performed by other models of computation.

Why is Church's Thesis important?

Church's Thesis is important because it provides a foundation for the study of computation and the limits of what can be computed. It also helps in the development of new computing technologies, as it allows for the analysis and comparison of different models of computation.

Is Church's Thesis universally accepted?

Church's Thesis is not universally accepted, as there are some alternative theories and models of computation that do not adhere to it. However, it is widely accepted as a fundamental principle in the field of computer science and mathematics.

How does Church's Thesis relate to the concept of computability?

Church's Thesis is closely related to the concept of computability, as it states that any effectively computable function can be computed by a Turing machine. This means that if a function can be computed by a Turing machine, it is considered computable according to Church's Thesis.

Similar threads

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

Hot Threads

Recent Insights

Back
Top