theorem 3.98 Church–Turing

open in the book · parts/02-mathematical-methods/01-logic-sets.tex:2859 · p. 52

Rests on

depends_on definition 3.93 Computable function, decidable set ¶
- depends_on definition 3.92 Turing machine ¶
depends_on definition 3.80 Formal system ¶
depends_on theorem 3.96 Turing ¶
- depends_on definition 3.93 Computable function, decidable set ¶ ↺
- depends_on definition 3.92 Turing machine ¶ ↺
- proves proof ch:01-logic-sets@proof-23 ¶
proves proof ch:01-logic-sets@prooflink-5 ¶

Supports

Nothing declares a dependency on this node yet.

Neighborhood

Every logical edge within two steps of this node.

declared and complete
partly declared
a check failed
not graded
declared in the source
inferred from structure

Edges

type	direction	node	provenance	where
`cites`	→	A Note on the Entscheidungsproblem	derived	parts/02-mathematical-methods/01-logic-sets.tex:2862
`cites`	→	On Computable Numbers, with an Application to the Entscheidungsproblem	derived	parts/02-mathematical-methods/01-logic-sets.tex:2862
`depends_on`	→	Computable function, decidable set	declared	parts/02-mathematical-methods/01-logic-sets.tex:2863
`depends_on`	→	Formal system	declared	parts/02-mathematical-methods/01-logic-sets.tex:2863
`depends_on`	→	Turing	declared	parts/02-mathematical-methods/01-logic-sets.tex:2863
`proves`	←	ch:01-logic-sets@prooflink-5	declared	parts/02-mathematical-methods/01-logic-sets.tex:2865