Download PDF
Representing natural numbers using states
Bitwise operations and the half- and full-adder
Subtraction on natural numbers
Adding and subtracting integers
Multiplication and division of natural numbers
Sequential logic
The difference engine
Sequential logic and finite-state machines
Regular grammars, regular languages, regular expressions, and Kleene's theorem
The stack and pushdown automatons
Context-free grammar and context-free langauges
The Chomsky hierarchy
Turing machines
Multi-tape Turing machines, Turing equivalence and Turing completeness
The Church–Turing thesis
Universal Turing machines, the fetch-decode-execute cycle, and Turing completeness
Non-deterministic Turing machines, additional complexity classes (including NP) and complement complexity classes (including co-NP)
Decidable languages
Reductions
Rice's theorem
Post correspondence problem
Entscheidungsproblem
Semi-decidable languages and recursively enumerable sets
Oracles and Turing reductions
The halting problem
Busy beaver
Stack machines, and their Turing equivalence
The analytic engine and its Turing-equivalence
Counter machines, and program counters (aka instruction pointers) and instruction registers; and Turing-equivalence of counter machines
Representing machine code with mnemonics
Random-access machines and pointers
Random-access stored-program machines
Implementing a stack using a register machine, the frame pointer, the stack pointer, the call stack, return addresses, and the stack buffer overflow
Simulating finite state machines with registers
Limited bit registers - 8-bit, 16-bit etc CPUs
External memory, the data bus and the address bus
Adding an Arithmetic Logic Unit (ALU) to a CPU
Advanced RISC Machines (ARM): mnemonics for mov and integer ALU instructions
Branches and jumps, loops and branch tables in ARM
External memory, the data bus and the address bus in ARM
ARM pseudo instruction: "="
ARM stack operations
Subroutines in ARM assembly
The Wheeler Jump
Assembling assembly code to machine code
Macros
text, data and bss
ARM floating point ALU
Extends the pushdown automaton.
To recap, the pushdown automaton had a stack which could be push to, popped, or an operation done on top values on the stack.
Stack machines are Turing complete.