Re: PROOF that numbers are countable
From: Will Twentyman (wtwentyman_at_read.my.sig)
Date: 05/12/04
- Next message: Eray Ozkural exa: "Re: Godel's Dualism (Re: Reflections Godel Wang)"
- Previous message: Michael Varney: "Re: My Experience as a "Non Gifted" Child"
- In reply to: |-|erc: "Re: PROOF that numbers are countable"
- Next in thread: The Ghost In The Machine: "Re: PROOF that numbers are countable"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Wed, 12 May 2004 08:01:22 -0400
|-|erc wrote:
> "Will Twentyman" <wtwentyman@read.my.sig> wrote
>
>
>>uninteresting or not part of your paradigm. I come back to it as a TM
>>where we need the godel number while we figure out if it halts.
>
> that's rather an entreched reason
Then please tell me how to *objectively* determine if a particular TM halts.
>>>Maybe you should examine the other side of the coin before arguing against it,
>>>see if you can hypothetically construct an indexing system of all computable functions.
>>
>>A function is computable if its TM always halts. How do you know if it
>>halts?
>
> somehow you have a godel number for it. notice you ignored my advice
How do you know it halts? It has a godel number.
How do you know it has a godel number? It halts.
To me it appears you are sidestepping the issue by restricting the
discussion to *some* of the TMs that halt. Or, you are not sidestepping
the issue and are talking as if you have solved it. I'm not certain
which it is because you haven't offered a construction, just an example
of one. I suspect you did not intend for your example to be complete,
but I could be wrong.
>>>There's maybe 4 or 5 simple ideas involved but because you are blindly arguing
>>>against it (as far as I can tell) I have to derive every step of the way.
>>>
>>>countable halting functions = clever godel numbering + labelless function paradigm
>>
>>You have found a way to represent *some* of the halting functions.
>>Great. You haven't shown how it compares with *all* of the halting
>>functions. You haven't shown what your representation can or cannot do.
>>
>>My concerns are theoretical, yours appear to be practical. The problem
>>is, the theoretical concerns appear to be at odds with your practical
>>claims. This is why I keep asking you to get down to the specifics,
>>such as defining your subclass of the halting functions in detail, then
>>analyzing what they can or cannot do. Please define them clearly, then
>>we can analyze what they can/cannot do. Right now, I'd be happy to have
>>a concrete definition we can look at.
>
> So would I, going that far was not even necessary to show that a complete
> set of halting functions may be enumerated.
The may be enumerated, but what if I want to know if a particular
function does not halt? How long do you suggest I wait for a
non-halting function before I give up on it?
>
> YOUR DIAGONAL PROOF CONTRADICTING THIS IS WRONG.
>
> I have nothing further to add on the topic. If you ignore half my posts then its getting stupid.
I'm not sure "getting" is the correct word.
> REPOST
>
>
>> 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.
>
> Different context though. Raw TMs don't have labels for states. 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.
>
>
> ==================================
> 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.
Or you could think of the tapes as being interleaved, so you can use a
standard tape.
> 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.
>
> 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.
How does UTM know if your TM/function halts on all values? That is the
question. Better, how does it know that a function does NOT halt for a
particular value? This is where the distinction between enumerating and
computing the halting TMs comes in. You can enumerate the halting
functions, but not the non-halting functions. You're claim appears to
be: UTM constructs a godel number for a TM *if and only if* the TM halts.
> 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. 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.
As you noted earlier, we both appear to be entrenched in our positions.
For the time being, I am content to believe that you don't realize the
halting problem deals with the issue of knowing a function does NOT
halt, not with knowing it does.
-- Will Twentyman email: wtwentyman at copper dot net
- Next message: Eray Ozkural exa: "Re: Godel's Dualism (Re: Reflections Godel Wang)"
- Previous message: Michael Varney: "Re: My Experience as a "Non Gifted" Child"
- In reply to: |-|erc: "Re: PROOF that numbers are countable"
- Next in thread: The Ghost In The Machine: "Re: PROOF that numbers are countable"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
