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

[Kreinovich, Vladik]

 Forwarding Yuri Gurevich's reply. 

-----Original Message-----
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
http://research.microsoft.com/~gurevich/annotated.html
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
strings.
    (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
linear time.
    (b) TM cannot compute with structures directly.  It turns out that
encoding structures as strings is far from innocent.  See #150 in this
connection.

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,
Yuri Gurevich

> From: Andrej Bauer [mailto:Andrej.Bauer at fmf.uni-lj.si]

>> 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?