Re: [Herc] Halting Problem Final Conclusion
From: |-|erc (gotch_at_beauty.com)
Date: 09/09/04
- Next message: peter_douglass: "Re: A question on GIT."
- Previous message: Thomas P.: "Re: Atheists dying"
- In reply to: Kent Paul Dolan: "[Herc] Halting Problem Final Conclusion"
- Next in thread: Kent Paul Dolan: "Re: [Herc] Halting Problem Final Conclusion"
- Reply: Kent Paul Dolan: "Re: [Herc] Halting Problem Final Conclusion"
- Messages sorted by: [ date ] [ thread ]
Date: Thu, 09 Sep 2004 12:09:36 GMT
"Kent Paul Dolan" <xanthian@well.com> wrote in >
> [attempts to educate the insane]
>
[Xanthian]
Results 1 - 10 of about 143 for author:kent author:paul author:dolan insane. (0.58 seconds)
I made your list!
[Herc]
NHalt2() = {2, 6, 33, 655, ..}
NHalt2 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
does not halt, otherwise it will return DONTKNOW.
As an example.
the program with godel number 999 is
10 goto 10
UTM(2, 999) = NOTHALT (ignoring the parameter of function 999)
UTM(6, 999) = DONTKNOW
UTM(33, 999) = NOTHALT
UTM(655, 999) = DONTKNOW
...
the program with godel number 1000 is
10 print 10
UTM(2, 1000) = DONTKNOW
UTM(6, 1000) = DONTKNOW
UTM(33, 1000) = DONTKNOW
UTM(655, 1000) = DONTKNOW
>From these outputs we can determine *without running the programs*
1/ program 999 does not halt
2/ program 1000 halts with probability of error 1/16.
[Simon]
Here's a quick sketch of a proof that no Turing Machine can list the
elements of NHalt2:-
Let's assume that there exists a Turing Machine, N, which lists the
elements of NHalt2.
Given N, we can easily construct another Turing Machine, H, which takes
the pair (f, a) as input, and does the following.
First, it simulates f(a) for a finite number of steps. If, by the end
of that simulation, f(a) has halted, H outputs 'halts', and halts. If,
instead, f(a) hasn't halted, H simulates N for enough steps for N to
give one element of NHalt2, n_1. It then simulates n_1(f, a). If
n_1(f, a) outputs 'does not halt', H outputs 'does not halt', and halts.
Otherwise, it resumes its simulation of f(a) for a further finite
number of steps. If f(a) still hasn't halted, it resumes its simulation
of N to get the next element of NHalt2, n_2, and simulates n_2(f, a),
and so on.
H keeps repeating this process until either f(a) halts, or an n produced
by N is reached such that n(f, a) outputs 'does not halt'.
If f(a) halts, H will reach that point in a finite number of steps. If
f(a) never halts, it will reach an n produced by N such that n(f, a)
outputs 'does not halt' in a finite number of steps. So, either way, H
will reach a final result in a finite number of steps.
We already have the classic proof that H cannot exist. Therefore, N
cannot exist.
--------------------------------------------------
I take it Xanthian is NOT capable of providing a proof that pHalt is not computable?
pHalt() outputs an infinite set of godel numbers that can be parsed by a UTM.
e.g.
pHalt() = {555,787,56554,445533, ...}
the program with godel number 999 is
10 print 10
UTM(555, 999) = HALT
UTM(787, 999) = HALT
UTM(56554, 999) = DONTKNOW
UTM(445533, 999) = HALT
UTM(77776677, 999) = DONTKNOW
Each of the pHalt functions has 50% chance of reporting if the program halts.
Is pHalt() computable? WHY?
Herc
- Next message: peter_douglass: "Re: A question on GIT."
- Previous message: Thomas P.: "Re: Atheists dying"
- In reply to: Kent Paul Dolan: "[Herc] Halting Problem Final Conclusion"
- Next in thread: Kent Paul Dolan: "Re: [Herc] Halting Problem Final Conclusion"
- Reply: Kent Paul Dolan: "Re: [Herc] Halting Problem Final Conclusion"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
