so-called Turing-Equivalence
01 Aug 1999 01:13:41 +0200

>: Vassil Nikolov <> in comp.lang.lisp

>> *in presence of interactions with the external world (including users)*?
> I am somewhat curious why you mention interactions.  One essential
> features of algorithmic machines such as a Turing machine is that
> there is no interaction with the external world as far as the
> execution of the algorithm is concerned (supplying the initial data
> (the initial contents of the tape) and collecting the result (the
> final contents of the tape) is outside the scope of theory of
> algorithms).  Therefore I don't see any meaning in relating
> Turing-equivalence to interactions with the external world.

I'm quite glad to see someone remember
what Turing machines and Turing equivalence are all about.

One of my points is _precisely_ that claims that
"being Turing-equivalent is not enough for a programming language",
or that "(Theoretical) Computer Science does not teach us anything
about language design" are utter nonsense;
for Turing-equivalence conspicuously does NOT apply
to programming languages with any I/O,
and it is certainly not the end-all of what theoretical computer science
has to say about language design.

And another point was that people use the term "Turing-equivalence"
without understanding at all what it was about (never mind the fact that
there even in common use within Algorithmic Information Theory,
there are _many_ _different_ concepts of "Universal" machines).

Optimae Salutationes (?),

[ "Faré" | VN: Уng-Vû Bân | Join the TUNES project!  ]
[ FR: François-René Rideau | TUNES is a Useful, Nevertheless Expedient System ]
[ Reflection&Cybernethics  | Project for  a Free Reflective  Computing System ]
There is no excuse for a programming language without clean formal semantics.
For even if your language is not designed for formal reasoning by computers,
there will still be humans who'll have to reason about programs.