Is this a true statement?

[Rainer Deyke]

"Tim Daneliuk" <tundra at tundraware.com> wrote in message
news:3B37A15D.DF05A331 at tundraware.com...
> Rainer Deyke wrote:
> > Consider this diagram of a typical computer program:
> >
> > Input -> Computation -> Output
> >
> > Only the "computation" part is algorithmic, and those who use the term
> > "Turing complete" generally only concern themselves with the computation
>
> Nope.  Formally, an "algorithm" is something which when presented with
> a given set of inputs will always produce the same output.  (This, BTW,
> is why Genetic Algorithms are a contentious case because given a
particular
> input, a GA will NOT give the same results repeatably.)  So, by the
> very definition of what an algorithm is and does, it embraces the notion
> of both input and output.

"Input" and "output" are physical actions.  A computer program cannot
necessarily manipulate the physical world, and "programming language A can
manipulate the physical world" does not imply "programming language B can
manipulate the physical world", even if both are Turing complete.

> Nope. *All* computation (including graphics generation) is reducable to a
> Turing Machine.

Which part of the Turing machine can emmit light?

>  In your example, the machine that turns things into
> graphics is itself a TM (if it is a digital computer) or it is the end
> analog device which is irrelevant to this entire discussion.

The end analog device is the entire point of the discussion.  Most
implementations of C++ can control it directly; Python cannot.

> > 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.

I challenge you to write a single computer program which, given the same
input, can produce more than one possible output.  Variances in operating
environment are part of the input.

>
> > generates output O from input I will always generate output O from input
I.
> >
>
> This is true for all things which are formally "algorithms".  But this
> is not the same thing exactly as "deterministic".

It is the same thing.  "Deterministic" = "Given this input, there can only
be one output".  Perhaps you are refering to the fact that the program is
designed to produce any one correct solution among many?  This is a human
interpretation.  The program doesn't know the problem it is trying to solve,
it only know the procedure by which it is trying to solve it, and the
procedure only has one possible result.

> > Only if the system has a writeable disk with sufficient empty space.
This
> > is not a given.
>
> Well no it's not, but this is irrelevant to the discussion.  Clearly, some
> implementations of any algorithm are more time/space efficient - Bubble
> Sorts run in O(n^2) but Heap Sorts run in O(n log n) yet both are still
> just sorting.  The limitations of disk, memory, and CPU merely define
> how big a problem we can solve, or how fast we can solve it, not *how
many*
> different kinds of problems we can solve, which is the debate here.
>
> For example, a machine with limited disk space can solve the same *set* of
> problems as a machine with Terabytes of disk, just much slower and less
> efficiently.  The minimums necessary to compute everything which is
> computable were defined initially by Turing and later by Bohm and
> Jacopini and in no case was disk space, memory space, or CPU speed
> a foundational condition.  As I said, these real-world constraints
> speak to how fast or how efficiently we can run a given algorithm,
> not how many *different* kinds of algorithms we can do.

Forget about the amount of disk space.  A device driver in C++ can run on a
system with *no* writable disk.  This is not true in Python.

> > "Net computational power" is irrelevant in this context.
>
> If you say so.  I thought this was the exact point of the debate: Can C++
> and Python "do" the same things.  i.e., Do they possess equivalent
abilities
> to compute the same set of problems - Computational Power.

"Doing" != "computing".  Get it now?


--
Rainer Deyke (root at rainerdeyke.com)
Shareware computer games           -           http://rainerdeyke.com
"In ihren Reihen zu stehen heisst unter Feinden zu kaempfen" - Abigor