Re (tilly) 4: Re-spect!: (OT) Where is programming headed?

[tilly]

I find your distinction between solvability and decidability somewhat interesting. I have not heard the distinction drawn that way. It has been a few years since I last looked at a book on this subject (and I gave away most of my math books about 4 years ago, so I don't even have one to look this up in right now), but I would think I would have remembered something like that.

So I did a quick Google search. And the funny thing is that I found lots of presentations online that disagreed with your proposed usage. I found none that agreed. For a random instance this lecture states directly that the Halting problem is not solvable.

And even when I look at your links, they say nothing about finite versus infinite. The classification they draw goes like this. A decision problem is a problem whose answers are all yes/no. A decidable problem a decision problem that is solvable. Solvable problems differ from decision problems in that solvable problems are not just limited to yes/no answers.

The fact that infinite answers are not accepted either for definitions of decidability or solvability is underscored by this lecture. They are very explicit about the fact that solvability and decidability both require that all of the computations involved halt. In other words you need to get an answer in due time.

Now you wouldn't just be making up your finite/infinite distinction, would you? Do you have a verifiable source you are willing to quote showing that someone else out there agrees with the usage you are claiming?

[mstone]

I think we're getting caught on the difference between defining a language, and proving that a given machine accepts a langauge by inspection. The former is axiomatic, and the latter is equivalent to the halting problem.

More fundamentals:

A Turing machine halts if it reaches either the accept or reject state for the given input.

If a Turing machine reaches the accept state for a given input, we say that the machine has recognized or proved that input. If a machine rejects an input, we say that the machine has disproved that input.

A total Turing machine halts for all possible input. Intuitively, a total Turing machine breaks breaks universe into two complementary sets: 'yes' and 'no'.

A non-total Turing machine doesn't reach the accept or reject state for some input. It breaks the universe into three sets: 'yes', 'no', and 'damned if I know'.

A language is the set of all strings that a Turing machine recognizes.

A language is recursive if the machine that accepts it is total. Recursive languages are provable because the machine can prove or disprove the membership of any possible input.

A language is recursively enumerable if the machine that accepts it is not total, i.e.: does not reach either the accept or reject state for every possible input.

Now, it's axiomatic that no Turing machine can read an infinite amount of input in a finite amount of time. If we declare all solutions that take infinite time to be indeterminate, no language that contains infinitely-long terms can be recursive. It can only be recursively enumerable.

Thing is, if we could reject the infinite terms, it would solve the halting problem. That doesn't work, so we can't use finite solution time as the criterion to decide whether a language is provable or not. It sounds you've accidentally conflated the idea of defining a language with the idea of proving a language by inspection. Officially incorrect, but easy to do if you're moving fast and not being totally anal about checking the math.

Now as to the halting problem:

If a set is recursively enumerable, it is semi-decidable. It will reach the accept state for every provable input, but will either reject or loop infinitely for unprovable input.

By that definition, we can build a lookup table that says whether any given program halts or not. We just can't do it in finite time. That same statement appears in the lecture you cited:

It should be noted that an unsolvable problem might be partially solvable by an algorithm that makes an exhaustive search for a solution. In such a case the solution is eventually found whenever it is defined, but the search might continue forever whenever the solution is undefined.

though I do agree that 'partially solvable' is a superior replacement for my phrase 'solvable, but only by inspection in infinite time'. It's shorter, and fits the heirarchy better.

mike
.

[tilly]

You just accurately regurgitated a good number of textbook definitions. Which isn't evidence of anything beyond your having access to a textbook or an equivalent online resource.

But none of your verbiage in any way, shape, or form addressed the direct question you were directly asked about your extremely unconventional use of the word "solvable".

Which is evidence that you are dodging the question.

A piece of friendly advice for the future. When you find yourself caught having made a mistake, admit it up front, and don't drag it out. People tend to forgive and forget when you do that. But when you put your foot in your mouth and proceed to attempt to get the rest of the leg in, the sight tends to stick in people's minds. Besides which, you simply aren't going to succeed anyways, and it is less work that way...