definition 3.92 Turing machine

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

Rests on

No declared or derived dependency edges point away from this node yet.

depends_on definition A.31 $k$-tape machine ¶
- depends_on lemma A.32 Tape reduction ¶
  - depends_on theorem A.33 thm:app-univ-universal ¶
depends_on definition 3.93 Computable function, decidable set ¶
- 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 ¶ ↺
depends_on lemma A.32 Tape reduction ¶ ↺
depends_on theorem A.33 thm:app-univ-universal ¶ ↺
depends_on theorem 3.96 Turing ¶ ↺
depends_on theorem 3.95 Universal machine ¶ ↺

Every logical edge within two steps of this node.

type	direction	node	provenance	where
`depends_on`	←	$k$-tape machine	declared	appendices/A-long-proofs.tex:2708
`depends_on`	←	Computable function, decidable set	declared	parts/02-mathematical-methods/01-logic-sets.tex:2736
`depends_on`	←	Tape reduction	declared	appendices/A-long-proofs.tex:2715
`depends_on`	←	thm:app-univ-universal	declared	appendices/A-long-proofs.tex:2773
`depends_on`	←	Turing	declared	parts/02-mathematical-methods/01-logic-sets.tex:2783
`depends_on`	←	Universal machine	declared	parts/02-mathematical-methods/01-logic-sets.tex:2766