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

Please select a chapter from the left.

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