Welcome to the Monastery PerlMonks

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

by mstone (Deacon)
 on Dec 18, 2001 at 04:52 UTC ( #132749=note: print w/replies, xml ) Need Help??

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
.

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

Replies are listed 'Best First'.
Re (tilly) 6: Re-spect!: (OT) Where is programming headed?
by tilly (Archbishop) on Dec 18, 2001 at 05:57 UTC
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...

Create A New User
Node Status?
node history
Node Type: note [id://132749]
help
Chatterbox?
 [Discipulus]: dabella12 if you dont use code tags no one will ever look at your problem

How do I use this? | Other CB clients
Other Users?
Others imbibing at the Monastery: (9)
As of 2017-06-24 14:20 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
How many monitors do you use while coding?

Results (558 votes). Check out past polls.