definition 3.93 Computable function, decidable set

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

Rests on

depends_on proposition A.15 Syntax is computable ¶
- depends_on theorem A.26 Diagonal lemma ¶
  - depends_on theorem A.27 Rosser ¶
depends_on theorem A.17 Representability ¶
- depends_on proposition A.28 prop:app-inc-derivability ¶
  - depends_on theorem A.29 Second incompleteness theorem ¶
- depends_on theorem A.30 Church, Turing ¶
- depends_on theorem A.26 Diagonal lemma ¶ ↺
- depends_on theorem A.27 Rosser ¶ ↺
depends_on theorem 3.98 Church–Turing ¶
depends_on theorem 3.96 Turing ¶
- depends_on theorem A.30 Church, Turing ¶ ↺
- depends_on theorem 3.98 Church–Turing ¶ ↺
- depends_on theorem 3.97 Rice ¶
depends_on theorem 3.97 Rice ¶ ↺
depends_on theorem 3.95 Universal machine ¶
- depends_on theorem 3.97 Rice ¶ ↺

Every logical edge within two steps of this node.

type	direction	node	provenance	where
`depends_on`	→	Turing machine	declared	parts/02-mathematical-methods/01-logic-sets.tex:2736
`depends_on`	←	Syntax is computable	declared	appendices/A-long-proofs.tex:1967
`depends_on`	←	Representability	declared	appendices/A-long-proofs.tex:2012
`depends_on`	←	Church–Turing	declared	parts/02-mathematical-methods/01-logic-sets.tex:2863
`depends_on`	←	Turing	declared	parts/02-mathematical-methods/01-logic-sets.tex:2783
`depends_on`	←	Rice	declared	parts/02-mathematical-methods/01-logic-sets.tex:2825
`depends_on`	←	Universal machine	declared	parts/02-mathematical-methods/01-logic-sets.tex:2766