Re: OPPOSITE OF all coin sequences are computable to infinite length ?

From: The Ghost In The Machine (ewill_at_sirius.athghost7038suus.net)
Date: 01/09/05 

Date: Sun, 09 Jan 2005 05:00:11 GMT

In sci.math, |-|erc
<h@r.c>
 wrote
on Sun, 9 Jan 2005 13:06:27 +1000
<34bld8F3n70r8U1@individual.net>:
>> >
>> > define a TM
>> > prove it is impossible
>> > define a number using impossible TM
>>
>> The TM for computing Chaitin's Constant is a mutation of
>> the TM for computing the halting problem.
>>
>> [spitsnip]
>>
>
> so you prove the halting value of some programs is unknown
> then you assign that to a variable, an unknown so to speak?

I'm not proving much of anything here. I'm simply stating
a result.

But, have it your way. Assume H is a machine with the following
characteristics.

[1] It always halts.
[2] If k = Enc1<m> concat ',' concat Enc2<i>, where m is
    a machine descriptor in some UTM formalism and i is
    a tape descriptor, and Enc1<> and Enc2<> are computable
    mappings into H's alphabet (sans ','), then H will
    write a 0 or 1 into the first cell of k
    (the rest of the tape will be munged).
[3] H will write 0 if m(i) will not halt, 1 if m(i) will.

If I've done this right, I can then construct another
machine W from H. W does the following.

[a] It looks for the comma, then replaces anything following
    with Enc2<beforecomma ',' aftercomma> , then moves the head
    back to the start of its input.
[b] It copies H. That is to say, the states of H are isomorphic
    to a proper subset of W's states, and the transitions of H
    are isomorphic to a proper subset of W's transitions.
[c] If the head is sitting over a 0, it halts and announces success.
    If the head is sitting over a 1, it loops.

W of course has a machine descriptor w. We can construct
k = Enc1<w> ',' Enc2<w>, and feed it to W.

Case 1: W(k) halts. This means that machine(w) on input w
does not halt. But machine(w) = W.

Case 2: W(k) loops. This means that machine(w) on input w
halts. But machine(w) = W.

Therefore H cannot exist.

In this machinery Chaitin's Omega can be construed as that number
such that the n'th bit is 1 if machine n halts on input Enc2<n>,
and 0 if machine n does not halt on input Enc2<n>. Very well-defined,
but not all that computable.

>
> X = of Halt(777)
> an unknown of the unknown. <gag>
>
> Y = "there is a god"
> what is the value of Y?

Y = false. But that's more properly addressed in talk.atheism. :-P

>
> Herc
> 

-- 
#191, ewill3@earthlink.net
It's still legal to go .sigless.

Relevant Pages

  • Re: Refutation of the DisProof of the Halting Problem
    ... EVERY function in the TM paradgim is void. ... But that couldn't be relevant to the halting problem, ... one thing when the input is an M,w pair where M halts on w, and one OTHER ... P halts on w and writes "loops" whenever P loops on w. ...
    (sci.logic)
  • Re: Hardware random generators and nondeterminsm
    ... the TM halts with the tape containing the nth digit ... computing until you get a non-9, but then to prove that this procedure ... always halts you need to prove that pi is irrational---something I daresay ... there is a polynomial time algorithm for computing pi to an error of plus ...
    (comp.theory)
  • Re: Is the Halting Problem merely an ill-formed question?
    ... It either halts or it doesn't; ... THEY CAN write on their tapes. ... if (MalignantSelfReference(SourceCode, InputData)) ... that the Halting Problem is solvable, I am only at most attempting to show the ...
    (sci.logic)
  • Re: The proof that I was referring to is on the website
    ... It does not go into an infinite loop if and only if it halts. ... >>This is how the Halting Problem is defined. ... It is not the analogy that is crucial. ... >>the student's could determine their own grades. ...
    (comp.theory)
  • Re: The proof that I was referring to is on the website
    ... It does not go into an infinite loop if and only if it halts. ... >>This is how the Halting Problem is defined. ... It is not the analogy that is crucial. ... >>the student's could determine their own grades. ...
    (sci.logic)