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