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

Andrej Bauer Andrej.Bauer at fmf.uni-lj.si
Sat Nov 3 15:29:47 EDT 2007


Kreinovich, Vladik wrote:
> May I add Yuri Gurevich's Abstract State Machines
> http://www.eecs.umich.edu/gasm/ 

Yes, this is definitely a model of computation that should be mentioned.
I am familiar with the uses of AST's for specifying models, developing
software, and other _applied_ uses. 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?

Best regards,

Andrej Bauer



More information about the FOM mailing list