[FOM] Simple Turing machines, Universality, Encodings, etc.

[Bruno Loff]

> Has anyone done any work on Abstract
> State Machines specifically geared towards computability theory, such as
> proving the Recursion Theorem, smn theorem, existence of non-computable
> c.e. sets, etc?

Boker and Dershowitz base their study of the CT thesis on the work of
Yuri Gurevich.

The full reference is:

Udi Boker and Nachum Dershowitz, 2007, "The Church-Turing Thesis over
Arbitrary Domains", Pillars of Computer Science: Essays Dedicated to
Boris (Boaz) Trakhtenbrot on the Occasion of His 85th Birthday, Arnon
Avron, Nachum Dershowitz, and Alexander Rabinovich, eds., Lecture
Notes in Computer Science, vol. 4800, Springer-Verlag, Berlin.

You may find a preprint at Nachum Dershowitz's web page.