piatra . institutepathwaysFinding the next step…
Connect automata, computability, undecidability and complexity through proofs and small executable models.
Comfort with simple algorithms and logical arguments helps. The Algorithms and Critical thinking routes are useful preparation; programming is optional for the first machine trace.
A recogniser, a reduction proof and an explanation of computability versus efficiency.
Start here if the background is new. Equivalent experience is enough.
Use algorithm traces and correctness arguments before studying recognisers and reductions.
Practise logical arguments and counterexamples before explaining a reduction proof.
Stanford Encyclopedia of Philosophy editors · reference
A simple transition table and worked machine trace
Check reading access
Open the readingCharles Petzold · book · 2008
A simple transition table and worked machine trace
Check reading access
Open the readingTuring Machines. Trace states, tape and head position in a small transition table.
The Annotated Turing. Use a worked explanation to follow the original machine model before reading its formal argument.
Alan Turing · paper · 1937
Definitions of recognition, decision and computability
Check reading access
Open the readingMichael Sipser · book · 2012
Definitions of recognition, decision and computability
Check reading access
Open the readingOn Computable Numbers, with an Application to the Entscheidungsproblem. Reconstruct the definitions and the diagonal step in a selected undecidability argument.
Introduction to the Theory of Computation. Distinguish recognition, decision and termination using the selected examples.
Hopcroft, Motwani · Ullman · book · 2006
Finite automata and binary-string recognition
Check reading access
Open the readingIntroduction to Automata Theory, Languages, and Computation. Use the finite-automata material to design and test a small language recogniser.
Alan Turing · paper · 1937
Definitions of recognition, decision and computability
Check reading access
Open the readingStanford Encyclopedia of Philosophy editors · reference
Diagonalisation and the scope of the Church–Turing thesis
Check reading access
Open the readingOn Computable Numbers, with an Application to the Entscheidungsproblem. Reconstruct the definitions and the diagonal step in a selected undecidability argument.
The Church-Turing Thesis. Separate the thesis about effective procedure from a theorem proved within a formal model.
Editorial perspectives based on selected works, rather than author-endorsed reading lists.
An editorial comparison of the route’s selected accounts and evidence.
A curated synthesis cannot be neutral or exhaustive. Follow the primary sources when an interpretation matters.
An editorial reconstruction using the selected work of Alan Turing.
This is not an author-endorsed syllabus. The reconstruction highlights selected works and may omit other commitments.
An editorial reconstruction using the selected work of John von Neumann.
This is not an author-endorsed syllabus. The reconstruction highlights selected works and may omit other commitments.
An editorial reconstruction using the selected work of Stephen Wolfram.
This is not an author-endorsed syllabus. The reconstruction highlights selected works and may omit other commitments.
Background, different viewpoints, and further reading.
Reconstruct the definitions and the diagonal step in a selected undecidability argument.
Definitions of recognition, decision and computability
Compare this account’s mechanism with the preceding reading; note where their predictions differ.
Full paper; methods and limitations
Extract one claim and distinguish the evidence supporting it from the author’s interpretation.
Selected chapters and argument
Use the finite-automata material to design and test a small language recogniser.
Finite automata and binary-string recognition
Compare running time with input size in one selected algorithm or problem class.
Input size, running time and complexity classes
Distinguish recognition, decision and termination using the selected examples.
Definitions of recognition, decision and computability
Extract one claim and distinguish the evidence supporting it from the author’s interpretation.
Selected chapters and argument
Use this account to revise your initial explanation and identify an unresolved question.
Selected chapters and argument
Use a worked explanation to follow the original machine model before reading its formal argument.
A simple transition table and worked machine trace
Compare this account’s mechanism with the preceding reading; note where their predictions differ.
Selected chapters and argument
Extract one claim and distinguish the evidence supporting it from the author’s interpretation.
Selected chapters and argument
Use this account to revise your initial explanation and identify an unresolved question.
Selected chapters and argument
Use the entry’s distinctions and bibliography to test the route’s central argument, rather than treating a summary as a substitute for the primary source.
Named section and worked examples
Trace states, tape and head position in a small transition table.
A simple transition table and worked machine trace
Separate the thesis about effective procedure from a theorem proved within a formal model.
Diagonalisation and the scope of the Church–Turing thesis
Distinguish decidability from tractability and identify the model behind a complexity claim.
Input size, running time and complexity classes
Use the entry’s distinctions and bibliography to test the route’s central argument, rather than treating a summary as a substitute for the primary source.
Named section and worked examples
Use the entry’s distinctions and bibliography to test the route’s central argument, rather than treating a summary as a substitute for the primary source.
Named section and worked examples
Use the entry’s distinctions and bibliography to test the route’s central argument, rather than treating a summary as a substitute for the primary source.
Named section and worked examples
Use the entry’s distinctions and bibliography to test the route’s central argument, rather than treating a summary as a substitute for the primary source.
Named section and worked examples