← Graph

Church-Turing Thesis

concept 2 connections

Thesis that whatever can be expressed by a Turing machine — or by its equivalents, lambda calculus and partially recursive functions — is what can be mathematically computed. Consequence: a problem a Turing machine cannot compute need not be run; it must instead be proven unsolvable within current mathematics or algorithms.

category
methodology
about
Church-Turing Thesis concept
Presented as the bridge between Turing machines, lambda calculus and partially recursive functions.
concept Church-Turing Thesis
related_to
Turing Machine concept
The thesis states Turing machines capture the notion of effective computation.

Provenance

Read by
1 extraction