so-called Turing-Equivalence

[Francois-Rene Rideau]

>: Tim Bradshaw <tfb@tfeb.org> on comp.lang.lisp

>>> Another formalism of equivalent power to a UTM is the lambda calculus
>>> Interestingly this formalism gave rise to an obscure and little-used
>>> family of programming languages, characterised mostly by their extreme
>>> slowness, unsuitability for any practical task, and the requirement
>>> for special hardware to run them with any degree of efficiency.

>> I'm _sick_ of hearing such a meaningless statement
>> of "being of equivalent power to a UTM" repeated over and over again
>> as a bad excuse for bad programming language design.

> I think you may be getting confused.  My article was in a thread
> asking a rather obscure and largely theoretical question about
> structure editors.  It wasn't about programming language design.
But as your full quote shows, you specifically used "Turing-equivalence"
as a concept meant to be relevant to language design,
and as your full post shows (not repeated here),
as a concept meant to be relevant to the "expressive power"
of programming languages.

> You may also perhaps have missed the fact that this last little aside
> to which you seem to have taken such offence was a joke.
I haven't missed the intended light tone of the remark;
I haven't missed either the implied acceptance of the widely replicated
but profoundly erroneous truism, that Turing-equivalence is
1) applicable _at all_ to tell anything about programming systems _with I/O_
2) the best criterion that Computer Science can say about such systems
 (with the implication that we must resort to superstition to do better)

"To argue that gaps in knowledge which will confront the seeker must be filled,
not by patient inquiry, but by intuition or revelation, is simply to give
ignorance a gratuitous and preposterous dignity...." -- H. L. Mencken, 1930

>> I question the meaningfulness of your term "Turing-equivalence".
>> What definition of it do you use, if any?
> 
> I think the definition in Boolos & Jeffrey `Computability and Logic'
> is as good as any.
That is, _not good at all_, considering programming of tasks _with I/O_.

> If I recall, they give quite a nice exposition of
> the various equivalent notions there (perhaps not talking about lambda
> calculus though).
Exposition that you seemingly didn't quite grok.
Equivalence is _always_ "up to" some transformations.
If you don't understand what these transformations are about,
when and where they do apply or not,
then you don't understand what the equivalence is about.

[ "Faré" | VN: Уng-Vû Bân | Join the TUNES project!   http://www.tunes.org/  ]
[ FR: François-René Rideau | TUNES is a Useful, Nevertheless Expedient System ]
[ Reflection&Cybernethics  | Project for  a Free Reflective  Computing System ]
The limit between philosophy and politics
is when you have to choose your friends.
		-- adapted from Karl Schmidt