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