---
title: "Church-Turing thesis"
subject: "Theory of Computation"
chapter: 5
key: "semester_3/theory_of_computation:church-turing-thesis"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/church-turing-thesis
site: BCT Engineering
---

# Church-Turing thesis

Theory of Computation · Chapter 5: Undecidability

- Asked in: 2071 Chaitra; 2072 Chaitra; 2072 Kartik (asked 3 times)
- Video: [The Church-Turing Thesis](https://www.youtube.com/watch?v=0D7yInuKvKs) — Neso Academy
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_3/theory_of_computation/church-turing-thesis
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-5

## Question

Explain the Church-Turing thesis. What is an "algorithm" according to the Church-Turing thesis? Why is it called a "thesis" and not a theorem?

## Short answer

Every effectively computable function can be computed by a Turing machine. An algorithm is a finite sequence of mechanical steps, halting on every input; it coincides with Turing-computability. It is a thesis, not a theorem, because 'effectively computable' is an intuitive notion, not formally defined, so it cannot be proved.

## Answer

#### Statement
The **Church–Turing thesis** says: **every function that can be computed by an effective procedure (an algorithm) can be computed by a Turing machine.** Equivalently, the intuitive notion of "algorithmically computable" coincides with "Turing-computable".

It was proposed independently by Alonzo Church (lambda calculus, 1936) and Alan Turing (Turing machines, 1936). Other formalisations were later shown to be equivalent in power: general recursive functions (Gödel, Kleene), Post systems, unrestricted grammars, register machines, and modern programming languages.

#### What is an algorithm?
By the thesis, an **algorithm** is a finite sequence of well-defined mechanical steps that can be carried out by a Turing machine and that **halts on every input**. A problem is **decidable** if some TM decides it (a machine that always halts and answers yes or no); a function is **computable** if some TM computes it.

#### Why a "thesis" and not a theorem?
- A theorem needs a mathematical proof. Here one side of the statement, "effectively computable", is an **informal, intuitive** notion with no formal definition, so the claim cannot be proved.
- It can be supported but not proved: every model of computation proposed so far (more than a dozen, such as lambda calculus and RAM machines) has turned out to be equivalent to Turing machines, and no counter-example has ever been found.
- It could in principle be disproved if some more powerful, physically realisable form of computation were discovered, but none is known.

#### Consequence
Showing that a problem is not solvable by any Turing machine (for example the halting problem) shows that it cannot be solved by any algorithm or program on any computer.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What does the Church-Turing thesis state?
   A. Every effectively computable function can be computed by a Turing machine
   B. Every TM halts
   C. Every language is decidable
   D. Turing machines are weaker than lambda calculus
   Answer: A. It equates intuitive algorithmic computability with Turing computability. (Key point: Statement)

2. According to the thesis, what is an algorithm?
   A. Any finite program that may loop
   B. A procedure carried out by a TM that halts on every input
   C. A PDA
   D. A regular expression
   Answer: B. An algorithm is a TM-computable procedure that halts on all inputs. (Key point: Algorithm)

3. Why is it a thesis and not a theorem?
   A. It is false
   B. 'Effectively computable' is an informal notion, so it cannot be proved
   C. It is trivial
   D. Nobody has checked it
   Answer: B. A proof needs formal definitions on both sides; the intuitive notion lacks one. (Key point: Why thesis)

4. What supports the thesis?
   A. Every proposed model (lambda calculus, recursive functions, etc.) is equivalent to TMs
   B. A formal proof
   C. Only Turing's model works
   D. Counter-examples
   Answer: A. All proposed models have proved equivalent and no counter-example is known. (Key point: Evidence)

## Related in Theory of Computation

- [Pumping lemma (CFL): aⁿbⁿcⁿ not CF](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Apumping-cfl-an-bn-cn) — Theory of Computation, chapter 3

## Related in other subjects

- [Algorithm for numbers divisible by 9 not 6](https://www.bctengineer.com/question.md?key=semester_1%2Fcomputer_programming%3Aalgo-flowchart-divisible-9-not-6) — Computer Programming, chapter 2
- [Banker's algorithm, 5 processes, 4 resources](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Abanker-five-process-four-resource) — Operating System, chapter 7
- [Recursion properties, Fibonacci, TOH algorithm](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Arecursion-properties-fibonacci-toh) — Data Structure and Algorithm, chapter 5
- [Algorithm and flowchart: distance between points](https://www.bctengineer.com/question.md?key=semester_1%2Fcomputer_programming%3Aalgo-flowchart-distance) — Computer Programming, chapter 2