Is this a true statement?

[Tim Daneliuk]

Brian McErlean wrote:
> 
<SNIP>
> 
> Output is not the same as computational ability.  The interfaces with
> which a program can output and interact with its environment have no
> effect on its computational power.  Postscript is turing complete, but
> 
> can't even access files.  Java is turing complete, and remains so when
> 
> you limit what it can access through its security model.


Right.  The "limitation" of one T-C language compared to another
is its *implementation* not the language itself.  This is what I've
been claiming throughout this thread because it sounded like 
people were claiming that one language could "do" more than another.
One *implementation* can certainly do more or less.

>
> 
> >> All computer programs are deterministic.  Any computer program that
> >
> >Nope. Not even close to true.  The entire family of NP-Complete algorithms
> >(Traveling Salesman, Knapsack Packing, et al) are NON-deterministic (that's
> >what the 'N' stands for.
> 
> This is incorrect.  There is no such thing as an NP-Complete
> algorithm, you  mean NPC _problems_.  This simply means that there is
> no (currently known) deterministic algorithm that can solve the
> problem in polynomial time.
> 
> The non-deterministic part refers to the fact that it _is_ possible to
> check whether a proposed solution is in fact correct, and so if you
> have a non-deterministic step that 'guesses' a solution, or you check
> all possible solutions in paralell, then you can potentially solve it
> in polynomial time.
> 
> The checking algorithm is still deterministic.  The NP part only
> refers to the time complexity of the problem, not the algorithm.  The
> problems are completely solvable with normal algorithms - they just
> take a long time.


I stand corrected.  You're absolutely right.

> 
> <snip>
> 
> >> > 2) Have Python write out a set of machine code bits which
> >> >    are understood by the underlying implementation and
> >> >    hardware to be the correct handling of an interrupt.
> 
> Actually, I don't think this is a valid solution to the problem.  If
> you define "writing a device driver in python" as equivalent to
> "writing a program in python that writes a device driver", then you
> violate the "purely in python" bit, because you're also writing it in
> C ( because the python interpreter is written in C, and it
> wrote/interprets a program (with your python program as input) that
> wrote the program that generated the device driver ;-)
> 

I am saying that there is some set of machine code bits which the
underlying system will understand as a device driver once it is
put in place (much like a C compiler compiles to loadable driver).
The set of bits can be generated by a Python program and never again
see the Python interpreter.


><SNIP>

> >
> >>
> >> > 3) Add a native interrupt object to the language.
> >> >
> >> > 1) clearly takes us out of "pure Python" and is thus of no further
> >> > interest (unless you actually want to *solve* this problem in the
> >> > real world, in which case this is probably the best solution ;)))
> >> >
> >> > 2) Works just fine, but is kind of clumsy and unnatural to use.
> >> > Note, however, that it is 2) that gives us the ability to do *anything*
> >> > in Python which we can "do" in any other Turing-Complete language.
> >> >
> >> > 3) is where the rocks start to get thrown.  If I do 3), have I "extended"
> >> > the language to do something it could not previously?  NO!  I have
> >> > implemented what I could already do with 2) in a more programmer-friendly
> >> > manner, but I have not changed the net computational power of the
> >> language.
> 
> But I don't think you can define the language as "anything it might do
> at  some future point in time, after I've added something."
> 
> If I add the complete possible C interfaces to postscript, I don't
> think I can call it postscript anymore, (unless I want a lawsuit
> whenever someone views a document that formats his hard drive).
> 
> If by "Python" you are referring to all possible future
> implementations of the language, then this is true, but you can still
> say "There are things possible in <foo> implementation of C, that are
> not possible with the standard distribution of python 2.1"

The only point that I was trying to make (apparently not well) is that
changes in implementation do not give a language new computational capabilites,
as such, they merely make it easier for the programmer to do things
that were impractical or limited by the implementation in the past.
The *language* always has the ability to do these things somehow.


------------------------------------------------------------------------------
Tim Daneliuk
tundra at tundraware.com