# Re: A modern view of the halting problem

*From*: "Dragontamer" <prtiglao@xxxxxxxxx>*Date*: 22 Oct 2006 18:57:55 -0700

Alex McDonald wrote:

Rod Pemberton wrote:

<randyhyde@xxxxxxxxxxxxx> wrote in message

news:1161530912.166161.254830@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

More importantly, you cannot write a program that

runs on a finite-resource machine (bounded memory, and program steps)

that determines if another program always halts and produces a correct

answer for all input values.

Before I ask the upcoming question, I'll simply state that I am not from a

CS background, and am _totally_ ignorant of the formal proofs of Church,

Turing, etc...

You've stated that it is impossible for one program to determine if another

program will halt. What I'd like to know is, is it possible to design a

language so that any program written in it will always halt properly,

whether or not that program is being reviewed by another program.

Basically, I'm asking why would one write a second program to check the

first program, if you know the first is correctly "halt-able" due to the

design of the language? I.e., is there some other proof, thereom, etc. that

says one can't design a provenly halt-able language...? At an assembly or C

level, it seems to me that you could halt every non-branching instruction,

and with correct design should be able to halt very branching instruction,

loop construct, or flow control code. I understand that I am missing

something to this discussion...

The halting problem is not about stopping at specific instructions;

it's about the impossibility of writing a program that can inspect

other programs and, in all cases, decide that they will halt or run

forever when executed.

I too am ignorant in this matter. But... I do recall a single example

that

seemed to make sense to me :-)

Lets take, the 4 color problem. Currently to my knowledge, it is

unsolved.

So lets ask a computer to find the first graph that contradicts the 4

color problem.

Now if the 4 color problem was solved, this would be easy to see if

the computer would halt or not.

Any algorithm that solved the halting problem would surely be

magnificent,

because it would obviously also solve any current math problem that

can be somehow expressed in a computer. (Including Riemann Hypothesis

and really, anything)

Or here is another actually, using Riemann Hypothesis instead.

Lets say algorithm A searches for a contradiction in the Riemann

Hypothesis.

(IIRC, there is a computer algorithm that really does that). Does A

halt?

Meh; this post doesn't "disprove" the halting problem nor does this

post "prove" it.

But it does at least show that the halting problem really is pretty

deep.

--Dragontamer

.

**References**:**A modern view of the halting problem***From:*Charles A. Crayne

**Re: A modern view of the halting problem***From:*Herbert Kleebauer

**Re: A modern view of the halting problem***From:*randyhyde@xxxxxxxxxxxxx

**Re: A modern view of the halting problem***From:*Rod Pemberton

**Re: A modern view of the halting problem***From:*Alex McDonald

- Prev by Date:
**Re: A modern view of the halting problem** - Next by Date:
**Re: A modern view of the halting problem** - Previous by thread:
**Re: A modern view of the halting problem** - Next by thread:
**Re: A modern view of the halting problem** - Index(es):