CH1 - part 1

Interprets and executes programs.

Processor

Stores programs and the data they process.

Memory

Transfers information between the computer and the outside world.

I/O equipment

A sequence of instructions followed by a computer to carry out a task.

Program

A step-by-step procedure for solving a problem or performing a computation.

Algorithm

The computer's main processor or 'brain.'

CPU (Central Processing Unit)

Fetches instructions from memory and interprets them.

Program Control Unit / Instruction Unit

Carries out arithmetic and logical/data-processing operations.

ALU (Arithmetic-Logic Unit)

Interprets instructions and makes sure they are performed in the correct sequence.

Control function

Performs the actual operations specified by instructions.

Execution function

Information represented using discrete values or symbols.

Digital information

Information represented by continuously varying quantities.

Analog information

A representation system that uses only 0 and 1.

Binary

A binary digit: one 0 or 1.

Bit

A computer that solves a problem using a program in a finite amount of time, rather than storing every possible answer.

Reasonable computer

An abstract computer model consisting mainly of an unbounded memory tape, a processor with states, and a read-write head.

Turing machine

The memory of a Turing machine, divided into squares that may be blank or contain symbols.

Tape M

The Turing machine component that has a small number of internal states and controls operations.

Processor P

The current internal condition or mode of a Turing machine processor.

State

Reads the current tape square, can replace its symbol, and can move left or right.

Read-write head

A blank tape square in the book's Turing machine notation.

b (blank)

Turing machine operation meaning move the read-write head one square to the right.

R

Turing machine operation meaning move the read-write head one square to the left.

L

Turing machine operation meaning halt the computation.

H

Represents a number n using a sequence of n ones.

Unary notation

A Turing machine that can simulate the operations of any other Turing machine.

Universal Turing machine

A problem for which no solution is currently known, although one may eventually be found.

Unsolved problem

A problem for which no general algorithm can ever solve all possible cases.

Undecidable problem

The undecidable problem of determining whether an arbitrary Turing machine with arbitrary input will eventually stop.

Halting problem

A machine with only a finite number of possible states because its memory is finite.

Finite-state machine

A problem that a practical computer can solve in a reasonable amount of time.

Tractable problem

A problem that may be solvable in principle but requires an impractical amount of computation or time.

Intractable problem

A method that generates or examines all possible cases.

Brute-force / exhaustive method

Describes how the amount of computation or running time grows as problem size increases.

Time complexity

Describes the order of growth of an algorithm's required work as input size n increases.

O(f(n)) / order notation

Accepts a sufficiently close result instead of requiring a perfectly exact result.

Approximation method

Uses a practical rule or strategy to find a good solution without exhaustively checking all possibilities; it does not guarantee the optimum.

Heuristic method

Associated with an early mechanical calculator capable of addition and subtraction.

Blaise Pascal

Associated with extending mechanical calculation to include multiplication and division.

Gottfried Leibniz

Babbage's machine designed to automatically compute mathematical tables using the method of differences.

Difference Engine

A technique that uses repeated additions and finite differences to evaluate polynomial values.

Method of differences

Babbage's proposed machine considered the first general-purpose programmable computer ever designed.

Analytical Engine

The memory component of Babbage's Analytical Engine.

Store

The arithmetic-processing component of Babbage's Analytical Engine, comparable to an ALU.

Mill