Re: [PO] Re: Attempt to Refute the Halting Problem's Refutation

From: Simon G Best (s.g.best_at_btopenworld.com)
Date: 08/22/04 

Date: Sun, 22 Aug 2004 01:39:02 +0000 (UTC)

Peter Olcott wrote:
> "Daryl McCullough" <daryl@atc-nycorp.com> wrote in message news:cg514q02lqt@drn.newsguy.com...
>
>>Peter Olcott says...
>>
>>>> 1. Define a set of programs S as follows: P is in S if
>>>> when P is run as a main program on input #P (which means the
>>>> code for P) the program halts and the result is 0.

'#P' means 'the code for program P', 'program P's code', 'program P as
code'.

I'll use 'result(P, x)' to mean 'the result from running program P on
input x', 'the result returned by program P when given input x'.

S = {P: P halts on #P, result(P, #P) = 0}

In other words: S is the set of all programs where each program P in the
set has the following two properties: P halts on #P; result(P, #P) = 0.

Programs which don't halt on their own code aren't in S. Programs which
do halt on their own code, but which don't produce the result 0, aren't
in S.

Do you agree that the set S exists? Do you agree that S is a
well-defined set?

>>>> 2. Define a mathematical function diag(x) as follows: if x
>>>> is a code for a program that is in set S, then diag(x) = 1.
>>>> Otherwise, diag(x) = 0.

           { 1 : [exists] P [in] S [such that] x = #P;
diag(x) = {
           { 0 : otherwise.

In other words: if x is the code for a program P, and P is in S, then
diag(x) = 1; otherwise, diag(x) = 0.

Do you agree that diag is a well-defined mathematical function?

>>>There is no option here to refuse to answer, thus the mathematical
>>>formalism abstracts away crucial details that could otherwise be
>>>used to form a solution.
>>
>>Do you agree, then, that diag(x) is a well-defined
>>mathematical function that cannot be computed by any
>>computer program?
>
> I am not sure about this I still don't fully understand this.

Suppose there is a program, D, such that result(D, x) = diag(x), and
which always halts, no matter what input it's given.

Is D in S?

         D [is in] S
     => (D halts on #D) [and] (result(D, #D) = 0)
     => diag(D) = 1
     => result(D, #D) = 1
     => D [is not in] S

A contradiction! Therefore, ~(D [is in] S).

         D [is not in] S
     => ~(D halts on #D) [or] (result(D, #D) != 0)

~(D halts on #D) implies that D doesn't always halt, which contradicts
the definition of D. We know, by definition, that D halts on #D,
because we defined D to halt no matter what input it's given. This
leaves us with result(D, #D) != 0.

         result(D, #D) != 0
     => diag(D) = 0
     => result(D, #D) = 0
     => D [is in] S

Another contradiction!

So, we have:

         D [is in] S <=> D [is not in] S

This is, of course, false, but does follow from the assumption that
there is such a program D. Therefore, D does not exist.

Therefore, diag cannot be computed by any computer program.

Do you understand it now? Has this helped?

:-)

Simon

Relevant Pages

  • Re: [PO] Re: Attempt to Refute the Halting Problems Refutation
    ... >>Peter Olcott says... ... do halt on their own code, but which don't produce the result 0, aren't ... Another contradiction! ... diag cannot be computed by any computer program. ...
    (comp.theory)
  • Re: Can a regular Turing Machine provide Protected Memory?
    ... I assume that you believe that you can construct a TM (a computer program) ... that can determine if any arbitrary program with any arbitrary input will ... These are all equivalent to Turing Machines (indeed, ... successfully predicts whether every program they throw at it will halt! ...
    (comp.theory)
  • Re: Can a regular Turing Machine provide Protected Memory?
    ... I assume that you believe that you can construct a TM (a computer program) ... that can determine if any arbitrary program with any arbitrary input will ... These are all equivalent to Turing Machines (indeed, ... successfully predicts whether every program they throw at it will halt! ...
    (sci.logic)
  • Re: What is the Result from Invoking this Halt Function?
    ... You have got to break PO of his habit of thinking of "the Halt analzyer" ... running computer program. ... The functions that TMs compute are ABSTRACT, ... That's one reason why you shouldn't go around saying "a halt analyzer". ...
    (sci.logic)
  • Re: Alan Turings Halting Problem is incorrectly formed
    ... >> It's just a fact about computer programs that no computer program ... > were submitted to see if the English Poem would halt. ... can't diagnose immortality its a paradox, and you can't diagnose functions that ...
    (sci.logic)