Is this a true statement?
Steven D. Majewski
sdm7g at Virginia.EDU
Sun Jun 24 21:45:37 CEST 2001
On 24 Jun 2001, Tim Daneliuk wrote:
> "Steven D. Majewski" wrote:
> >
> > Wrong, David.
> > Turing completeness means that anything you can *COMPUTE* in one
> > language you can computer in another. Python, Lisp, C++, etc.
> > are all equivalent in that sense.
> >
> > But you can't *DO* all of the same things in all languages -- for
> > example: you can write a device driver in a language if you can't
> > specify interrupt vectors or hardware address pointers.
> >
>
> Not so, Steve. If something is Turing-Complete you CAN do everything
^^^^^^^^^^^^^^^^^
> in that language - it just may be ugly. All Turing-Complete languages
> (like C, BASIC, Assembler, C++, Python...) can compute *exactly* everything
> which is computable and therefore exactly what each of the other T-C
> languages can compute. They will do so with different degrees of effectiveness
> (which corresponds to their suitability for the problem at hand) and efficiency
> (which corresponds to Turing machines of different computational complexity) but
> they are all *equivalent* in functionality.
Be careful, Tim!
David was very precise in his wording and we were talking about a
specific example with no precise requirements. ( Somebody one said
that vague requirements are easy to fill -- for a *perfectly* vague
specification, any program will suffice! )
[ See my other posts for my concession. ]
I don't retract the statement that the fact that you can compute
any computable function in any Turing complete does not mean that
you can *DO* the same thing in any language.
The one is a theoretical statement that has a formal proof.
The other is a practical statement that requires a empirical proof.
( "DO" means to perform. )
If you disagree, I'll be happy to provide a challenge task for you
to perform that will leave you mired in the "Turing Tar-pit" !
-- Steve Majewski
More information about the Python-list
mailing list