Le 07-juil.-06, à 07:23, Tom Caylor a écrit :
>> Exercise: show that the functions from N to {0,1} are not enumerable,
>> by a similar proof. Hint: find the appropriate slight change in the
>> definition of g.
>>
>
> Change g to
>
> g(n) = (Rn(n) + 1) mod 2
OK. other solution, change g to
g(n) = 1 - Rn(n)
> One way to think about this is to concatenate the output of each Ri and
> put a decimal point (actually binary point) in front of it to make a
> number between 0 and 1, expressed in binary. Each Ri is arbitrary,
> say,
>
> output of R1 = 0.101...
> output of R2 = 0.010...
> output of R3 = 0.100...
> ...
OK. Just be careful: 0.0111111111111111... and
0.10000000000000000000000... are equal. Find the precise correspondence!
> but each R1 is infinitely long, since the domain of each Ri is the
> natural numbers N (i.e. each Ri is total). If the domain wasn't all
> of N, then the diagonalization wouldn't work. Right?
The diagonalization always work, but it will prove something different.
The fourth case will illustrate that.
>
> So
>
> g(1) = (R1(1) + 1) mod 2 = 0
> g(2) = (R2(2) + 1) mod 2 = 0
> g(3) = (R3(3) + 1) mod 2 = 1
> ...
>
> and so concatenating these together into a binary number from 0 to 1
> gives
>
> output of g = 0.001...
>
> which is different from any of the Ri's. So here we see Cantor's
> original diagonal proof of the uncountability of the real numbers
> played out in binary.
Indeed.
> I have to repeat though that I have misgivings about using infinite
> diagonalization to try to conclude things about real-live reality
> (physics, mind/body problem).
Remember that I *assume* comp. Like George Levy says: I assume that
there is a level of description of me such that "my personal
experience" (consciousness) is invariant for digital substitutions made
at that level. And I assume Church thesis, and AR (Number Realism).
> We indeed are using the law of the
> excluded middle with an infinite sequence.
Er...
> We are saying that since g
> cannot be any particular one of the Ri's, then g is not in the whole
> infinite list. I know that this particular diagonalization is not one
> that is used in your argument,
Nice. Indeed. It is a key point.
Actually, with Loewenheim Skolem, Cantor's diagonalization can be shown
to be relative. The notion of "non enumerability" is relative to a
theory). I guess you hear about Skolem "Paradox"?
> but I think that the same fault is in
> the other diagonalizations.
It is up to you to show this, but Church thesis is exactly what makes
the notion of "non recursive enumerability" absolute.
Godel didn't want to believe in it, but after reading Turing, he called
it an epistemological miracle.
I think it is the comp possibility of nothing least that a
(neo)platonist negative theology, somehow.
> Not that this can't be used to argue about
> "imaginary" mathematical play things like the set of real numbers, or
> the other creatures that come out of the following diagonalizations,
> but how can we say that these things have anything to do with reality?
Some of those diagonalization shows that computer are always
"crashable", a fact which can be of some interest for militaries ...
More seriously, it is normal that once we assume comp, computer
science, especially the fundamental one, can say something about "us"
(in some large sense of "us").
Even more especially after the UDA reasoning shows that physics emerges
from 1-comp indeterminacy.
Remember I was just trying to make more concrete Smullyan's heart of
the matter. The key is Church thesis, and then incompleteness, and then
provable (by the machine) incompleteness.
I will show how to translate the 1-indeterminacy in term of
incompleteness through variant of the self-reference modal logic G and
G*.
> I know you'll probably say that it's testable, but I have yet to see
> it. Diagonalization is not testing. Diagonalization just produces
> negative results. Something doesn't exist. How can we test that?
We can't. But I never need to do that. It is only the physical theory
extracted from the comp hyp which can be tested.
How? Well if the comp-physics predict that an electron weight one ton,
we could have to revised comp, ok?
> In this post, you don't say that the functions are "effectively
> computable", just "computable". Is effectiveness implied?
Yes. Even without Church thesis all the following term are equivalent:
Turing computable
Post computable
Java computable
Rational unitary matrices computable,
etc.
With Church thesis, they are all equivalent with:
Intuitively computable
effectively computable
In some (intensional) context effectivity could mean more, but to talk
about that now would be confusing. Could say more after the fourth
diagonalization solution. Not today.
> I thought
> that computable meant just codable as an algorithm, you can program it,
> and effective means it also takes a finite amount of time to produce
> its output.
No. If there is an output, you always get it in finite time. Could be
long ... though.
> I think I've read that computable can mean effectively
> computable. Is this the case here?
Yes sure.
>
> So does mechanically generable basically mean that you can write a
> finite program that will be able to generate the code for all of the
> functions in the sequence? In other words, simply having the infinite
> list of programs "hardcoded" into the program wouldn't qualify, because
> then the program (that generates the code for the functions) would be
> infinitely long. So mechanically generable (same as RE?)
Yes. It is a version of Church thesis in term of generable set, instead
of computable function.
Church thesis can be shown (and I will do it probably, or suggest how
to show that if we pass near by) equivalent with:
mechanically generable = recursively enumerable = computably enumerable.
> means that
> the set of functions is such that it can be ordered so that it follows
> some pattern that can be compressed into a finite set of rules. Right?
Yes. A code, program, indice, number, some-recognizable-finite-thing,
...
>
> (By the way, Wikipedia is hard to follow here. Without re-looking it
> up, I think that the definitions of "computable" and "recursively
> enumerable" seem mutually circular, so I've found it hard to pin them
> down.)
>
> So in other words we've proved that the whole set of total computable
> functions is *not* such that it can be ordered so that it follows a
> pattern that can be compressed into a finite set of rules (algorithm).
Yes. In the sense that we have shown that there is no program capable
of generating
ALL AND ONLY ALL codes of total computable function. (1)
The set of such codes is NOT recursively enumerable.
But we can still believe that we can encode all total functions
compressed in a finite set of rules or program.
It will follow necessarily by (1) that such a program will generate
ALL codes of total computable functions but only AMONG other beasts.
What will the diagonalization prove then? (= the fourth one).
>
> Again, I'll be interested to find out how this relates to reality in a
> testable way.
I'm afraid that for really getting the essence of this, you will need
to pass the UDA exam :-)
If not, well it is enjoyable theoretical computer science.
Must go, I will comment the rest of your post tomorrow.
Bruno
http://iridia.ulb.ac.be/~marchal/
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Everything List" group.
To post to this group, send email to everything-list.domain.name.hidden
To unsubscribe from this group, send email to everything-list-unsubscribe.domain.name.hidden
For more options, visit this group at
http://groups.google.com/group/everything-list
-~----------~----~----~----~------~----~------~--~---
Received on Fri Jul 07 2006 - 13:12:36 PDT