Re: PROOF that numbers are countable

From: The Ghost In The Machine (ewill_at_aurigae.athghost7038suus.net)
Date: 05/13/04 

Date: Thu, 13 May 2004 04:00:11 GMT

In sci.logic, |-|erc
<gotchy@beauty.com>
 wrote
on Mon, 10 May 2004 00:15:32 GMT
<EQznc.29972$TT.12127@news-server.bigpond.net.au>:
> That proof looks very complicated, he says [the conclusion
> was the assumption] the same line of approach I am using,
> except my claim is the subassumption was some programs don't
> halt, I think his claim is the assumption is the halting function
> would be impossible....though I don't know how he would demo that.
> I might read it when I'm off the mind torture satellite,
> I basically can't concentrate on anything, for 2 years I've been
> forced into constant tangential thoughts by a bunch of nazi like
> interrogators..... ha suck ... one just said via the satellite
> that follows me everywhere.

Uh...right.

Well, all programs eventually *do* halt (when the power goes out,
if nothing else). This is supposed to be a theoretical thing.

>
>
>> 1$: JNZ 1$
>> (We assume here that '1$' is a local label; there's at least
>> one assembler that supports such a concept.)
>
> Here's your problem, it doesn't matter if 1000 compilers run a
> paradoxical program, you only need one compiler that is consistent.

Compiler? I'm talking assembly language here. A local label
is a perfectly consistent concept.

As for paradoxical: the microprocess runs anything thrown at it.
It's *stupid*. If one codes

1$: JMP 1$

and feeds it in, the micro will happily run until reset.
(A variant of this instruction set was in fact actually
used in VMS 3.7; IIRC it was called the "null process", and
ran at a very low priority. Subsequent operating systems
(and possibly a subsequent version of VMS) inserted a HLT
in the loop, for efficiency.)

>
> Different context though. Raw TMs don't have labels for states.

Yes they do, just not of this sort. A formal description of a TM
includes:

- an alphabet, a series of symbols readable from and writable to tape.
- a state list, a series of states for the machine transitions.
- a start state.
- a set of accepting or halting states.
- a transition function: domain alphabet x state, range
  state x {left, right, stay_put}.

I'd have to look if I've done it right but one can construe the
state list as a list of state labels, although internally one
will probably just use numbers as you suggest; I suspect
most implementations do.

> Any encoding of the states will result in some kind of numerical
> list. This list is only accessible by that one TM itself.
> That TM, if it was given a numerical index (think godel number),
> is only accessible by the UTM.
>
> Say we encode the UTM to a TM number (godel number) its 999.
>
> We can get the UTM to run the UTM represented on the tape.

ITYM "TM", not "UTM", in the second case. As it is, you are correct,
but it would be rather complicated. Also, the location of the emulated
state is of some interest.

>
>
>==================================
> UTM
>
> tape
> 0 0 0 0 0 0 0 0 9 9 9 0 0 0 0 0 0 0 0 8 6 0 0 0 0 0
>===================================
>
>
> We'll allow a simple juxtaposition of the godel numbers to
> perform function application, to allow an infinite tape in
> both directions for each function would require emulating 2 tapes.
>
> This function is UTM(UTM(86)
> Which is the same result as running TM86.
>
> Now to create a modified diagonal, G(j) = UTM(j,j) mod 2 + 1,
>
> To access UTM(j,j) it must be encoded on the tape!!!!!!
> UTM(j,j) would be
>
> tape
> 0 0 0 0 0 0 0 0 9 9 9 0 0 0 0 0 0 0 0 j 0 0 0 0 0 j 0 0
>
> tape
> 0 0 0 0 0 0 0 0 9 9 9 0 0 0 0 0 0 0 0 8 6 0 0 0 0 0 8 6 0 0 0
>
> e.g. when j = 86
>
>
> Next step :
>
> Create a modified UTM that applies the program to its own godel number
> for its parameter. Say it has encoding 1111.

Not permissible. The Godel number of a UTM cannot be placed
within the UTM, as that modifies the UTM.

>
> tape
> 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 8 6 0 0 0 0 0
>
>= UTM(j,j)
>= J(j)
>
> When j = 1111
>
> tape
> 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 10 0 0
>
>= UTM(1111,1111)
>= mUTM(1111)
>= UTM(1111,1111)
>
> UTM cannot calculate modifiedUTM.
>
> The wrong conclusion : this contradiction means numerical
> encoding of functions is impossible. (G actually adds 1
> to make mUTM a contradiction, one step further!).
>
> The right conclusion : The UTM encoding has some protocol
> for recognising constructions of emulator type functions,
> and won't construct a godel number for them unless it halts
> on all values. This is allowable since we can program UTM any
> way we want.

Actually, no. A UTM must be a TM, unless you wish to add
additional scratch tapes or something (which wouldn't be
all that much of a change since one can simply skip over
the input, write two blanks, then shift the input in
such a way that at the end of the say one has a non-blank
followed by 2 blanks followed by a non-blank; the general
effect would be a bit like uncoiling a string).

As it is, I'd be curious as to how you'd determine that a
machine "halts on all values". There are an infinite
number of tape possibilities (more precisely, the
number of symbol combination increases without limit),
although only a finite number of states, which might help.

I'll have to work on whether I can construct a TM that
computes f(i,n+1) given f(i,n) on the tape, where:

f(i,0) = i, for i > 0

f(i,n+1) = f(i,n) if f(i,n) = 1 [halt and accept]
f(i,n+1) = 3 * f(i,n)+1 if f(i,n) is odd and > 1, for n >= 0
f(i,n+1) = f(i,n)/2 if f(i,n) is even, for n >= 0

The machine's mission in this case is to compute the minimum n
such that f(i,n) = 1, given i on the tape.

(There's a name for this function/paradox but I'd have to look.
It's rather famous and AFAIK as yet unproven.)

>
> Hope that helps, you seemed to get it before, no use me keeping
> on declaring something everyone denies. Although you seem to
> be in the boat you can apply diag at another level.

It is not possible to diagonalize on a list of computable functions.
The reason is that a computable function has a finite spec;
the diagonal function does not.

It *is* possible to diagonalize on a list of (non-computable) reals.

> I don't think so, programs compile into numbers, its as simple
> as that, people found some <<high level>> contradictions and
> panicked and forgot they could count.
>
> Herc
>
>
>
> \ oo
> \____|\mn
> / /_/ /\ \_\ - FREE THE TRUeMAN -
> / K-9/ \/_/ - Join www.chatty.net -
> /____/_____\ - Webmasters join www.BannerX.net -
>
> "The Ghost In The Machine" <ewill@aurigae.athghost7038suus.net> wrote > >> >> >
>> >> >> > Don't get you knickers in a knot Will, the purpose of my argument
>> >> >> > is the Halting Proof has limited scope, no use shouting its in the textbook.
>> >> >>
>> >> >> Erm...what precisely is the scope of the Halting Proof?
>> >> >>
>> >> >
>> >> > Maybe you can field some of these questions, you did agree
>> >> > that Barbs diag attack had a limitation didn't you?
>> >>
>> >> It's not Barb's, it's Cantor's. But yes, it has limitations.
>> >> For example, if one lists all of the rational numbers' decimal
>> >> expansions in a list, and attempts to construct a diagonal,
>> >> it doesn't work.
>> >
>> > no, Cantor only worked with reals, Barb was using the same diag
>> > approach on functions. Do you forget what you agreed to?
>>
>> Yes.
>>
>> But here's a tidbit for you, which proves that the Halting Problem
>> is formally decidable and that Cantor's diagonalization proof
>> is invalid:
>>
>> http://www.deducing.com/rott.html
>>
>> I've not analyzed it in detail.
>>
>> >
>> >
>> >>
>> >> Also, if one lists the result of all parameterless computable
>> >> functions (after eliminating the ones that don't halt), the
>> >> diagonal isn't a computable function.
>> >>
>> >> > What was that limitation?
>> >>
>> >> The limitation is that the diagonal has to be effectively the
>> >> same form as the original numbers.
>> >>
>> >> > Maybe you
>> >> > should paraphrase YOUR understanding of anything I've demonstrated,
>> >> > when you write like so 'yes ... that means this' its difficult
>> >> > to put forward your stance.
>> >>
>> >> You have claimed to demonstrate that the reals are denumerable.
>> >> At least, such is my understanding.
>> >
>> > Just answer the question. I said demonstrated not claimed.
>>
>> That is your claim.
>>
>> >
>> > You have a short memory, you said "YES I AGREE BARBS APPROACH IS WRONG,
>> > SORRY BARB, THERE ARE PROBLEMS USING DIAG"
>>
>> That is correct; Barb's approach was indeed wrong for computable functions.
>> It has to do with the same logic that the above paper uses; a Turing
>> machine can be shown not to halt if it reenters a state.
>>
>> >
>> > Now you completely forget why you said that. You've jumped into the thread
>> > for the subject not what you replied to. Try google. Try to remember why
>> > you agreed Barb was wrong. Fucking backflip county this group.
>>
>> For the record (and from memory):
>>
>> Let L be a list of Turing machines. Each Turing machine has a finite
>> descriptor, which is usually listed as a table of states and
>> state transitions. The "diagonal machine" L(D) cannot exist,
>> as it does not have a finite descriptor. Therefore the usual proof
>> is invalid and one must look for alternative methods.
>>
>> A more classical proof:
>>
>> Let S1 be an arbitrary program (we'll call this a
>> *subroutine*) taking a single argument (pushed on the
>> stack) and returning a single result in R0 (we assume
>> here sufficient [*] registers to solve the problem,
>> sufficient stack, arbitrarily large integers, and JSR
>> and RET instructions, among other things). Let s1 be an
>> encoding of S1 and let U be a program that can take s and
>> simulate it.
>>
>> What is U? Well, erm, it cannot be an S1, unless one gets
>> cute and encodes the input and the algorithm. Of course
>> it makes life interesting that we can't say whether an
>> arbitrary listing of code C is even a subroutine Sn, let
>> alone an S1.
>>
>> We now enter a Russel's like hierarchy of types, and the
>> usual proof of diagonalization doesn't quite work here, either.
>> The proof looks like this:
>>
>> "Let P be a program, with encoding p, and let H(p) be
>> a routine that takes a single argument and"
>>
>> oops, possible problem already; P is not assumed to take any inputs.
>> However, this doesn't appear to be a major flaw yet. [+]
>>
>> "indicates whether P halts or not. If P halts, H(p)
>> returns 1 in R0. If P does not halt, H(p) returns 0."
>>
>> A formalism.
>>
>> "Let h be H's encoding.
>> Let Q be the program
>>
>> Q: CALL H
>> 1$: JNZ 1$
>> MOV #0, R0
>> RET
>>
>> (We assume here that '1$' is a local label; there's at least
>> one assembler that supports such a concept.)
>>
>> Q takes a single argument, namely an encoding number for a
>> program. If the encoding number is for a halting program,
>> Q loops. If the encoding number is for a non-halting program,
>> Q returns 0. Encode Q in q."
>>
>> And there's the diagonalization argument. Do you see it?
>> We now finish:
>>
>> "Now call Q with q. Does Q halt on this input? If so, then
>> H(q) would return 1, which means the local loop loops endlessly.
>> Oops. Well, maybe Q doesn't halt on this input. Then
>> H(q) would return 0, which means Q halts and returns 0.
>> Double oops. Therefore Q is impossible. Since Q depends on
>> the existence of a subroutine H, H is impossible. QED."
>>
>> The diagonalization argument works here because we're
>> making no assumptions about P -- P could consume stack,
>> push things on the stack, munge up registers, even crash
>> by going off the end of the stack (which counts as a halt,
>> I suppose). If we restricted H to work on S1-type programs
>> only, we'd have difficulties constructing Q as Q would
>> either have to be an S2 (as H is an S2), or one would have
>> to encode the input to Q using a function E -- the simplest
>> method is a digit interleave of the two arguments. If H
>> only worked on S0-type programs, Q could take no inputs,
>> although one can attempt to work around that fairly simply
>> by modifying Q to be:
>>
>> Q1: PUSH #q1
>> CALL H
>> 1$: JNZ 1$
>> MOV #0, R0
>> RET
>>
>> The problem *here* is that Q1 cannot contain its own encoding.
>>
>> So now we have to get cute. If we assume three additional programs,
>> all of them fairly easy to construct, we might get somewhere.
>>
>> Let E be a program that takes two inputs (it's therefore an S2), and
>> returns the interleaved output in R0. Let D1 and D2 take an encoded
>> output from E and return one of the original two inputs; D1 returns
>> the first digit string, D2 the second. D1 and D2 are S1's exclusively.
>>
>> If we restrict H to working on S1's, H cannot work on E.
>> Oops! (Fortunately, E halts anyway. I leave the proof to the
>> interested reader.) It turns out H is an S2 as well, as it
>> takes two inputs: s1 (the encoding of the program being tested) and
>> the input to S1. Therefore H cannot work on itself -- h -- as well.
>> This is not an insurmountable problem, as it turns out; we simply
>> assume the construction of the program J, which does the following:
>>
>> J: POP R0 ; get input parameter
>> PUSH R0 ; save it back
>> CALL D1 ; decode first integer
>> MOV R0, R1 ; save it
>> POP R0 ; restore original input
>> PUSH R1 ; first parameter to H
>> CALL D2 ; decode second integer
>> PUSH R0 ; second parameter to H
>> CALL H ; call program under test
>> RET ; and return result
>>
>> Now we call J after calling E to get our "magic token". J is an S1
>> so can be fed as an input to H.
>>
>> We construct Q2 in more or less the usual fashion.
>>
>> Q2: CALL J
>> 1$: JNZ 1$
>> MOV #0, R0
>> RET
>>
>> Q2 is an S1, as J is an S1. Encode Q2 in q2, then call E again
>> with q2 as *both* parameters -- call this result eq2. Hmm...there's
>> that diagonalization argument again.
>>
>> We now call Q2, with eq2. Q2 calls J, J calls H with the arguments
>> q2, q2. H tests Q2 to see if it halts on input q2. Oops, that
>> won't work; we've not closed the loop.
>>
>> So your result more or less stands; the specific halting decidability
>> problem remains unresolved. (The general halting problem is of course
>> unsolvable anyway; the first proof in this post is not affected by
>> all this.)
>>
>> None of this helps in setting up a viable H, of course; this is
>> strictly a "proof by destruction". :-)
>>
>> >
>> > Herc
>> >
>>
>> [*] infinite, really -- but infinity is a concept.
>>
>> [+] one of the more interesting flaws of a program is to take data
>> it's not supposed to -- from the stack, for instance, or an
>> uninitialized register. Such bugs can be devilish to ferret out
>> in production code until one sees what's going on.
>>
>> --
>> #191, ewill3@earthlink.net
>> It's still legal to go .sigless.
>
> 

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