[FOM] FW: Simple Turing machines, Universality, Encodings, etc.
vladik at utep.edu
Sat Nov 3 23:30:48 EDT 2007
Forwarding Yuri Gurevich's reply.
From: Yuri Gurevich [mailto:gurevich at microsoft.com]
There is plenty of theoretical ASM research.
As far as computability goes, the ASM computation model is equivalent to
the Turing machine (TM) model which is a better tool for undecidability
results. One pedagogical advantage of the ASM model is in teaching
computability theory to students who are better in programming than
math; see #179 at
in this connection.
The equivalence survives if you restrict attention to polynomial time
computations on strings. However, situation changes if you consider (a)
finer complexity classes or (b) computations with structures rather than
(a) For example, TM linear time is no good e.g. for computational
geometry. ASMs allow you to capture any natural notion of linear time.
In #118, we tried (to start) to address the issue of lower bounds for
(b) TM cannot compute with structures directly. It turns out that
encoding structures as strings is far from innocent. See #150 in this
But the thrust of ASM research has been on the theory of algorithms
rather than the theory of computable functions. #164 is a relatively
recent survey. Let me mention also that sometimes it makes sense to
think of algorithms even if you are interested only in computable
function; #190 is a good example.
Thank you for the interest. Best regards,
> From: Andrej Bauer [mailto:Andrej.Bauer at fmf.uni-lj.si]
>> May I add Yuri Gurevich's Abstract State Machines
> Yes, this is definitely a model of computation that should be
> I am familiar with the uses of AST's for specifying models, developing
> software, and other _applied_ uses. Has anyone done any work on
> State Machines specifically geared towards computability theory, such
> proving the Recursion Theorem, smn theorem, existence of
> c.e. sets, etc?
More information about the FOM