so-called Turing-Equivalence
01 Aug 1999 00:59:27 +0200

>: Stig Hemmer <> on comp.lang.lisp

> Turing-equivalent == being able to solve [exactly] the same problems
> as a Turing Machine.
A completely pointless definition,
since it forgets the most important point about equivalence,
which is "up to what transformations?".
If you accept no transformation at all, then trivially,
only Turing Machines are equivalent to Turing Machines.
If you allow "any" transformation, then as trivially,
everything is Turing-equivalent, including your neighbour's mother's socks.

> A Turning Machine has infinite memory, which means that no physical
> machine can be Turing-equivalent.  So, this is a purely theoretical
> concept.
A "concept" has infinitely precise extent, which means that no physical
phenomenon can be a concept. So yours is a purely theoretical statement.

>> Do these transformation correspond to anything _remotely_ meaningful
>> *in presence of interactions with the external world (including users)*?

> I believe it can be made meaningful(well-defined), though trying to
> give an exact definition would be beyond the scope of this article.
Trying to give an exact definition would be _quite_
within the scope of the current discussion.
Oh, certainly, you could contort some meaningful definition
(and there is not a One True One) of Turing-equivalence among pure systems
to kind of work on systems with external interactions,
but you would end up with a completely irrelevant contorted concept.

> It is, however, not very interesting.
You miss the whole point.

> The problem isn't the external world really.  It is rather that
> Turing-equivalence say nothing about 
>  -  ease of programming.  A big issue in the real world.
>  -  execution speed.  Another big issue in some contexts.
This "real" world of yours is but the "external" world,
to the computing system. And speed can very well be formalized
within an interaction framework, too. So that
1) The problem IS about interactions with the external world
2) Since (badly taught) concepts of Turing-equivalence are _conspicuously_
 not applicable to systems with I/O,
 any claim that they do not provide data
 about programming systems with I/O shows deep inadequacy
 not of the many concepts of Turing-equivalence in general,
 but rather of the bogus understanding of people about these concepts.

[ "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 ]
The degree of civilization in a society can be judged by entering its prisons.
		-- F. Dostoyevski