Commentary by Chris Pressey

This work is distributed under a CC-BY-ND-4.0 license, with the following explicit exception: the ratings may be freely used for any purpose with no limitations.

Theory of Computation

Computation: Finite and Infinite Machines

• rating: classic

There are lots of books on computability, but this is one of the earlier ones (1967!) and one of the few that treat "Turing tarpits" with any seriousness.

The Universal Turing Machine

• rating: 3

Contains a very interesting collection of papers about universal Turing machines and related things.

Theory of Recursive Functions and Effective Computability

• rating: TODO

Similar to a book I read by R. I. Soare.

Automata and Computability

• rating: 1

Decent textbook, but has a slightly disjointed feel (you can really tell it came from a set of lecture notes).

But there is some good stuff in here, like the VALCOMPS proof that the emptiness of the intersection of two CFLs is undecidable.

Also the product construction for finite automata.

Also some stuff about the arithmetic hierarchy and stuff.

Theory of Computation

• rating: 0

There are lots of books on computability. This is one of them. I don't think it's the best one, but it's the one that defines the programming language "PL" and, more interestingly, PL's primitive recursive subset PL-{GOTO}, for which Cat's Eye Technologies has implemented a compiler to ilasm.

Theories of Computation

• rating: 1

A very different approach to expositing the theory of computation, starting with clones (a kind of closure system).

Computability Theory, Semantics, and Logic Programming

• rating: TODO

Somewhat interesting, will have to read: a computability textbook, but starting from a PROLOG-like language (EFS by Raymond Smullyan) instead of the usual Turing Machine type stuff.

Theory of Deductive Systems and its Applications

• rating: 3

Wow, just wow.

The author presents a theory of deductive systems. The basic definition of a deductive calculus is essentially a Post Canonical System, cleaned up a little bit:

A canonical calculus is of the form (A, P, a, 𝜋) where A and P are disjoint alphabets (A is terminal symbols, P is variables), X is a set of axioms (words of A), and 𝜋 is a list of inference rules. Each inference rule is of the form "From S1, ... Sn, deduce S0", where each Si is a word in (A ∪ P). S1 to Sn are the premises, S0 is the conclusion. S0 must not contain any variables that the premises don't have.

Derivation is accomplished through pattern matching. Assign words to each of P. The word assigned to P is its value. In S1 to Sn, replace each member of P with its value. If every one of the resulting S1' to Sn' are members of X (the axioms), replace also those members of P in S0 with their values to obtain a new word, and add that new word to X. Repeat until exhausted.

In general, such systems describe logical calculi, in which relations can be derived - i.e. strings (theorems) can be derived from given strings (axioms), and such a derivation is a proof. But the process is in general nondeterministic, so to determine if a particular chosen string can be derived from particular axioms, a search must be made.

But later in the book Maslov takes an extended view and uses these calculi to describe all manner of things. And I really do mean all manner. That, plus the general character of some of the writing, justifies the "Wow, just wow."

Why is the Turing machine considered effective computation if it's not realizable due to the Bekenstein bound?

• rating: 1

.

Other Undecidable Problems (wayback)

• rating: 1

.

Scooping the Loop Snooper --- Geoffrey K. Pullum

• rating: 1

.

Shtetl-Optimized » Blog Archive » Rosser's Theorem via Turing machines

• rating: 1

.

Are there any undecidability results that are not known to have a diagonal argument proof?

• rating: 1

.

Is there a finite-dimensional vector space whose dimension cannot be found?

• rating: 1

.

Algorithmic Information Theory

• rating: TODO

.

The Limits of Reason (Gregory Chaitin)

• rating: 1

.