Fundamentals of Computing by Leonid A. Levin

1 Models of Computations; Polynomial Time & Church’s Thesis. 2
1.1 Deterministic Computation:

The simplest models are most useful for proving negative results and the strongest ones for positive results.

Computations consist of events and can be represented as graphs, where edges between events reflect various relations.

Time: The greatest depth D_{A(x)} of causal chains is the number of computation steps.

1.2 Rigid Models:

Rigid computations have another node parameter: location or cell. Combined with time, it designates the event uniquely. Locations have structure or proximity edges between them. They (or their short chains) indicate all neighbors of a node to which pointers may be  directed
1.3 Pointer Machines. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4 Simulation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2 Universal Algorithm; Diagonal Results. 6
2.1 Universal Turing Machine. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2 Uncomputability; Goedel Theorem:

Computable (partial and total) functions are also called recursive (due to an alternative definition). Their ranges (and, equivalently, domains) are called (recursively)  enumerable or r.e. sets. An r.e. set with an r.e. complement is called recursive (as is its yes/no characteristic function) or decidable. A function is recursive iff its graph is r.e. An r.e. graph of a total function is recursive. Each infinite r.e. set is the range of a 1-to-1 total recursive function (“enumerating” it, hence the name r.e.).
2.3 Intractability; Compression and Speed-up Theorems. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3 Games; Alternation; Exhaustive Search; Time v. Space. 9
3.1 How to Win. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.2 Exponentially Hard Games. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.3 Reductions; Non-Deterministic and Alternating TM; Time and Space. . . . . . . . . . . . . . . . . . . 11
3.4 Fast and Lean Computations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4 Nondeterminism; Inverting Functions; Reductions. 13
4.1 Example of a Narrow Computation: Inverting a Function. . . . . . . . . . . . . . . . . . . . . . . . . . 13
4.2 Complexity of NP Problems. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
4.3 An NP-Complete Problem: Tiling. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
5 Randomness in Computing. 16
5.1 A Monte-Carlo Primality Tester. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
5.2 Randomized Algorithms and Random Inputs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
5.3 Randomness and Complexity. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
5.4 Pseudo-randomness. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
5.5 Cryptography. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s