"Jim Balter" <j...@balter.name> wrote in message
news:i2fkp7$2i...@digitalmars.com...
"Peter Alexander" <peter.alexander...@gmail.com> wrote in message
news:i2er6d$1jk...@digitalmars.com...
On 24/07/10 12:43 PM, Jim Balter wrote:
I thought that this was exactly the halting problem.
A common misconception, but not so. The halting problem is to find an
algorithm that will, for every possible function and data as input,
correctly determine whether the function will terminate. Turing proved
that such an algorithm is impossible, but that's irrelevant to any
practical problem. Not only isn't it necessary to guarantee that the
functions you decide not to attempt CTFE on really don't terminate, but
no function in any real program looks anthing like the arcane function
that Turing proved will baffle your algorithm.
Walter is right.
No, he's not, and I explained why, and you have failed to rebut anything I
wrote.
Yes, Turing did prove it using an unrealistic example, but the only
reason he did so was to keep the proof simple.
You have no absolutely no idea what you're talking about; Turing's proof
is reductio ad absurdum based on a diagonalization argument -- the
constructed undeterminable function is dependent on the algorithm
purported to be able to decide it. See
http://en.wikipedia.org/wiki/Halting_problem
There are plenty of practical examples of functions which are difficult
(or impossible) to determine whether or not they terminate.
The halting problem proof isn't about "diffiicult", only "impossible", and
you have failed to provide a function and a proof that it is *impossible*
to determine whether it terminates.
In particular, any recursion or unconstrained loops make it very
difficult to prove termination, and there's plenty of practical examples
of those e.g. quicksort.
Again, difficulty is not an issue, *impossibility* is -- *that* is what
the halting problem is, and if you don't understand that then you don't
understand the issue *at all*.
P.S.
The point about difficulty goes to why this is not a matter of the halting
problem. Even if the halting problem were decidable, that would not help us
in the slightest because we are trying to solve a *practical* problem. Even
if you could prove, for every given function, whether it would halt on all
inputs, that wouldn't tell you which ones to perform CTFE on -- we want CTFE
to terminate before the programmer dies of old age. The halting problem is
strictly a matter of theory; it's ironic to see someone who has designed a
programming language based on *pragmatic* rather than theoretical
considerations to invoke it.
