Re: before Cantor there was Rantor

From: |-|erc (spam_at_fodder.abc)
Date: 10/18/04 

Date: Mon, 18 Oct 2004 22:44:18 GMT

"Barb Knox" <see@sig.below> wrote in message
> "|-|erc" <spam@fodder.abc> wrote:
>
> >"Barb Knox" <see@sig.below> wrote in ...
> >> "_|erc" <spam@fodder.abc> wrote:
> >> [snip]
> >>
> >> >I'm not an advocate of
> >> > hypothetical
> >> > abstract diagonal
> >> > contradiction
> >> > conclusion
> >> >type proofs, especially the results they 'deduce'.
> >>
> >> Now that IS curious. Not that you're opposed to diagonal proofs in general
> >> (such as Peter Olcott was), but that you make a SINGLE EXCEPTION to that
> >> "rule". Namely, you seem to accept the result of the proof that there is no
> >> computable function which solves the Halting Problem. The proof of that is
> >> EXACTLY of the form which you claim to universally reject:
> >>
> >> 1. Hypothesise that there is some function which solves the Halting
> >> Problem.
> >> 2. Construct a diagonal function (using that hypothetical function as a
> >> component) which defeats the hypothetical function when it's given the
> >> diagonal function as input.
> >> 3. That's a contradiction, since the hypothetical function was hypothesised
> >> to work correctly for all inputs.
> >> 4. Thus we conclude (Reductio ad Absurdum) that the hypothesis is false,
> >> i.e. that there is NO such function.
> >>
> >> So why don't you reject that result also?
> >
> >
> > *abstract* diagonal
> >
> >halting proof is contradiiction of the existence of a particular defined
> >function.
>
> No, it's a contradiction of the hypothesis that ANY such function exists.

that is abuse of language. get it through your head. anti-diag is ANY number,
halt function is a SPECIFIC function. can you see the difference?

if anti-diag had *some* tangible property then they would be in the same abstract/tangible class.

anti-diag is indistinguishable from any other number, we know nothing about it at all.
halt function is the supposed function that .... insert definition here.

halt function is NOT GCD. halt function is NOT GPS. halt function is NOT AES.

is there *any* real real number you can specify that anti-diag is NOT?

> The function certainly can not be concretely "defined" (e.g. programmed),

define doesn't mean program! define means specify, its a very limited scope
where the specification is the actual code..

> since the proof shows that no such program can exist in the first place.

HAHAHAHA

>
> And I don't understand the distinctionn you're trying to make between an
> "abstract" diagonal and some other kind -- it's hard to think that anything
> could be more abstract than the hypothesised Halting-solver, which by its
> very essence can not exist!

more backwards cyclic reasoning. abstract =/= impossible

>
> >this defintion is (can be) independant of the set of all functions,
>
> No, it's dependent on the fact that the Halting-solver is hypothesised to
> identify exactly the subset of all computable functions that halt. The
> "all" is crucial, because that means when it fails for even one instance
> (the diagonal) then it fails full stop.

yes I saw this later but its only a parameter, its not part of the makeup of the actual
code of the halt function.

every algorithm depends on a natural input, but its definition is not *composed* of
the definition of naturals, except from a pedagogical p.o.v.

>
> >the real-diagonal is dependant on the set of all reals.
>
> In exactly the same manner, ISTM.

anti-diag is not distinguishable to any other real
halt is distinguishable to other functions. ergo it has a valid definition

>
> I know you desperately want to defend the Halting Problem diagonal proof
> while simultaneously rejecting diagonal proofs in general, but why bother?
> Why not go the unreformed Olcott route and reject the Halting Problem proof
> too?

I did disprove the Halting Proof. Why do you think the discussion suddenly halted around here
when I posted this?

halt(f, a) -> pHalt2(n) -> P(UTM(n, f(a))='halt') = 0.5
!halt(f, a) -> pHalt2(n) -> UTM(n, f(a))='don't know'

pHalt2 is an (infinite) set of functions that satisfy pHalt below, with the added
contraint P(UTM(n, f(a))='halt') = 0.5. Therefore a randomly selected pHalt
function has 50% odds of answering the halt program for some given input.

(different set notation)
halt(f, a) -> En, n e pHalt, UTM(n, f(a))=true
!halt(f, a) -> An, n e pHalt, UTM(n, f(a))='don't know'

For example, pHalt could be an infinite set of Universal Turing Machines,
but they timeout after various amounts of time. If the parameter f(a) halted
in that time then it outputs TRUE, otherwise it timed out and outputs DONTKNOW.
Since the number of these partial Halt functions is infinite, we should come across
one with enough test cycles to determine if any function halts.

By itself pHalt is still useless as it only gives one output value, HALTS. But if
each pHalt function has 50% chance of being correct (something more powerful
than the UTM), then determining NOTHALT is a simple probabilistic procedure.

e.g.
pHalt2() = {2, 6, 33, 655, ..}

i.e.
pHalt(2) = true
pHalt2(6) = true
pHalt2(33) = true
..

pHalt2 is an infinite set of godel numbers whos functions can be parsed by a UTM.

each of these functions has independant probability of 50% of answering if the input function
halts, otherwise it will return DONTKNOW.

As an example.

the program with godel number 999 is

10 goto 10

UTM(2, 999) = DONTKNOW (ignoring the parameter of function 999)
UTM(6, 999) = DONTKNOW
UTM(33, 999) = DONTKNOW
UTM(655, 999) = DONTKNOW
...

Since :
!halt(f, a) -> pHalt2(n) -> UTM(n, f(a))='don't know'

the program with godel number 1000 is

10 print 10

UTM(2, 1000) = HALT
UTM(6, 1000) = DONTKNOW
UTM(33, 1000) = HALT
UTM(655, 1000) = DONTKNOW

Given :
halt(f, a) -> pHalt2(n) -> P(UTM(n, f(a))='halt') = 0.5

>From these outputs we can determine *without running the programs*
1/ program 999 does not halt with probability of error 1/16
2/ program 1000 halts

A *solution* to the halting problem is apparent, but it cannot be fully represented as
an *algorithm*, so the halting proof will fail here to surface a contradiction.

Herc

Relevant Pages