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

Algorithms for integer multiplication

Algorithms for integer division, modulus and remainders

Calculating natural number square roots

Identifying primes

Factorising natural numbers

Arrays

Reversing arrays

Reductions on arrays

Sorted arrays and bubble sort

Selection sort

Insertion sort

Searching sorted and unsorted arrays

Filtering and slicing arrays

Concatenating arrays

Merging sorted arrays

Decision problems

Correctness of algorithms

Measuring algorithmic complexity with big-O notation

P (PTIME), EXPTIME, DTIME and simulation by Turing-equivalent machines in polynomial time

Hardness of problems and completeness of problems in a given complexity class

L (LSPACE), PSPACE, EXPSPACE, DSPACE

The relationships between P, L and PSPACE

Search problems and reducing them to decision problems

Optimisation problems and reducing them to decision problems

Counting problems and their complexity classes (including \#P)

Function problems and their complexity classes (including FP)

Polynomial-time reductions

Log-space reductions

Simple lossless compression

Please select a chapter from the left.

This is a live document, and is full of gaps, mistakes, typos etc.