Re: Alan Turing's Halting Problem is incorrectly formed (PART-TWO)

From: Eray Ozkural exa (erayo_at_bilkent.edu.tr)
Date: 06/25/04 

Date: 25 Jun 2004 05:18:31 -0700

"Peter Olcott" <olcott@worldnet.att.net> wrote in message news:<i5rCc.21964$OB3.15265@bgtnsc05-news.ops.worldnet.att.net>...
> > > PREMISES:
> > > (1) The Halting Problem was specified in such a way that a solution
> > > was defined to be impossible.
> >
> > No, it wasn't. It's a perfectly legitimate mathematical problem. It's
> > not even obvious that it wouldn't have an effective solution at first
> > sight.
>
> function LoopIfYouSayItHalts (bool YouSayItHalts):
> if YouSayItHalts () then
> while true do {}
> else
> return false;
>
> Does this program Halt?

This is a particularly useless program which has nothing to do with
the halting problem.

The program loops forever if it is given true as input, otherwise it
terminates. That is, its termination depends on the input.

> (Your (YES or NO) answer is to be considered
> translated to Boolean as the function's input
> parameter)

The answer is not a simple yes or no, and why should my answer be fed
back to the function?

** Type mismatch. Sorry.

(Yes, I'm a good computer)

> Please ONLY PROVIDE CORRECT ANSWERS!

Sure. But let's work on the halting problem the way Alan Turing posed
it, okay? In more modern terms, of course, the Turing Machine is too
low level for some people to understand.

HALTING PROBLEM: Let U be a universal computer. Let w be a program
string and x be an input string. U(w,x) denotes the computation of
program w with input x. The computation U(w,x) is said to be halting
if it terminates and outputs a string y=U(w,x) after a finite number
of steps. Is there a program p such that U(p, [w,x])=1 if U(w,x) halts
and U(p, [w,x])=0 if U(w,x) does not halt for all w and x, where [w,x]
denotes the encoding of pair (w,x)?

This is a legitimate question, although the proof seems too easy to
believe. If we didn't know the proofs, then we would be considering
that it might be possible for such p to exist, since it is possible
for a program to examine the code for input program w and data x, and
make a decision. Unfortunately, it turns out that any p can decide the
halting problem for only a finite number of input programs, and not
for all inputs as the problem asks.

Regards, 

--
Eray Ozkural

Relevant Pages

  • Re: Alan Turings Halting Problem is incorrectly formed (PART-TWO)
    ... > Does this program Halt? ... But let's work on the halting problem the way Alan Turing posed ... string and x be an input string. ... if it terminates and outputs a string y=Uafter a finite number ...
    (sci.logic)
  • Re: ot hypocrites for christ
    ... represented as a string, ... representation of an algorithm, and i is some input string. ... You DO (or halt does, ... we've shown the halting problem ...
    (alt.sports.basketball.nba.la-lakers)
  • Re: Disproof of the Halting Problems Conclusion
    ... The state transition from qto ) ... don't know state transition graphs well enough. ... > just a random string. ... >> Since the state transition diagram version of the Halting Problem ...
    (sci.logic)
  • Re: simple and beauty strategy
    ... the halting problem is a decision problem ... Alan Turing proved in 1936 that a general algorithm to solve the ... the program will eventually halt when run with that input. ... undecidability of a problem in the lambda calculus had already been ...
    (rec.gambling.lottery)
  • Re: The Halting Problem is merely an erroneously formed question
    ... Since you are asserting that this machine must eventually halt, you are therefore asserting that this machine has entered an invalid run state, and you are breaking the implicit model of computation. ... This may be a mental fiction, but you can make these assumptions fully explicit in descriptions and talk about real world machines in the same manner. ... the halting problem itself is not the most useful problem to solve. ... word games that are harder to play in mathematical notation. ...
    (comp.theory)