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
Find a halting program of a given size which produces the most output possible.
Describes a Turing machine with an alphabet of \(2\) symbols.