![History [of undecidability]](/nks/img/thumbnails/notes-12-8--history-of-undecidability--textonly.png "History [of undecidability]")
![[Undecidability in] natural systems](/nks/img/thumbnails/notes-12-8--undecidability-in-natural-systems--textonly.png "[Undecidability in] natural systems")
![[Classes of] fast algorithms](/nks/img/thumbnails/notes-12-8--classes-of-fast-algorithms--textonly.png "[Classes of] fast algorithms")
![History [of computational complexity theory]](/nks/img/thumbnails/notes-12-8--history-of-computational-complexity-theory--textonly.png "History [of computational complexity theory]")
![Lower bounds [on computational complexity]](/nks/img/thumbnails/notes-12-8--lower-bounds-on-computational-complexity--textonly.png "Lower bounds [on computational complexity]")
![[One-sided] Turing machines](/nks/img/thumbnails/notes-12-8--one-sided-turing-machines--textonly.png "[One-sided] Turing machines")
![Functions [computed by Turing machines]](/nks/img/thumbnails/notes-12-8--functions-computed-by-turing-machines--textonly.png "Functions [computed by Turing machines]")
![[Turing] machine 1507](/nks/img/thumbnails/notes-12-8--turing-machine-1507--textonly.png "[Turing] machine 1507")
![Properties [of example Turing machines]](/nks/img/thumbnails/notes-12-8--properties-of-example-turing-machines--textonly.png "Properties [of example Turing machines]")
![Longest halting times [in Turing machines]](/nks/img/thumbnails/notes-12-8--longest-halting-times-in-turing-machines--textonly.png "Longest halting times [in Turing machines]")
![Growth rates [of halting times]](/nks/img/thumbnails/notes-12-8--growth-rates-of-halting-times--textonly.png "Growth rates [of halting times]")
![[Turing] machine 600720](/nks/img/thumbnails/notes-12-8--turing-machine-600720--textonly.png "[Turing] machine 600720")
![[NP completeness in] natural systems](/nks/img/thumbnails/notes-12-8--np-completeness-in-natural-systems--textonly.png "[NP completeness in] natural systems")
![Implementation [of TM cellular automaton]](/nks/img/thumbnails/notes-12-8--implementation-of-tm-cellular-automaton--textonly.png "Implementation [of TM cellular automaton]")
![Satisfiability [emulating Turing machines]](/nks/img/thumbnails/notes-12-8--satisfiability-emulating-turing-machines--textonly.png "Satisfiability [emulating Turing machines]")
![[Intractability in] systems of limited size](/nks/img/thumbnails/notes-12-8--intractability-in-systems-of-limited-size--textonly.png "[Intractability in] systems of limited size")
![[Computational complexity of] finding outcomes](/nks/img/thumbnails/notes-12-8--computational-complexity-of-finding-outcomes--textonly.png "[Computational complexity of] finding outcomes")
Undecidability in cellular automata
[Undecidability in] natural systems
Undecidability in tiling problems
Computational complexity theory
History [of computational complexity theory]
Lower bounds [on computational complexity]
Functions [computed by Turing machines]
Properties [of example Turing machines]
Longest halting times [in Turing machines]
Growth rates [of halting times]
[NP completeness in] natural systems
Non-deterministic Turing machines
Implementation [of TM cellular automaton]
Satisfiability [emulating Turing machines]
[Intractability in] systems of limited size