Date: Oct 25, 2005 6:30 PM
Author: Arthur J. O'Dwyer
Subject: Re: On NP Completeness and Intractability


On Tue, 25 Oct 2005, Willem wrote:
>
> stephen@nomail.com wrote:
> ) Noone was talking about indefinite input. The Halting Problem
> ) is unsolvable and there is nothing indefinite or uncertain about
> ) the input.
>
> It may be interesting to mention that the halting problem is most certainly
> solvable for some inputs, and it might even be that it is solvable for
> almost all inputs, it's just that it's not solvable for *all* inputs.


"Solvable for almost all inputs" doesn't make sense in this context,
I think. After all, I can give you an algorithm that solves the Halting
Problem for about half of all valid inputs, and another that solves it
for all the rest:

Algorithm A. Return "true".
Algorithm B. Return "false".

Unfortunately, that doesn't lead to any useful insights. :)


If you define a mapping from the natural numbers to Turing machine
programs, then you might be able to say interesting things about the
fraction of correct answers to incorrect answers in the first 'n'
programs (given by some specified algorithm), as 'n' goes to infinity...
but you'd have to come up with a really clever mapping in order to
prove anything about it, and IMHO no such clever mapping exists.

-Arthur