Re: Cardinality of Set of Computable Numbers?
From: George Greene (greeneg_at_greeneg-cs.cs.unc.edu)
Date: 12/30/03
- Next message: Arthur J. O'Dwyer: "Re: Cardinality of Set of Computable Numbers?"
- Previous message: George Greene: "Re: Cardinality of Set of Computable Numbers?"
- In reply to: Russell Easterly: "Re: Cardinality of Set of Computable Numbers?"
- Next in thread: George Greene: "Re: Cardinality of Set of Computable Numbers?"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: 30 Dec 2003 13:33:57 -0500
The x you are trying to talk about DOES NOT EXIST.
"Russell Easterly" <logiclab@comcast.net> writes:
: > 1 x differs from every s that does not end with (0).
Then x is NOT FINITE. Remember, the INITIAL input tape WAS
finite -- it DID end with (0) (otherwise, how could it ever have
been generated in the first place?). If the output/result x
does not also end with (0), then there are 1's at arbitrarily
great distances out on it (i.e., for every place on it, there
are infinitely many 1's coming after that place, not all in a row,
but intermittently, every now and then, infinitely often, without
bound). This means that no TM COULD EVER RUN LONG ENOUGH
to produce all these 1's. If x does not end with (0), then x
is NOT THE OUTPUT of a TM that ran on an input that DID end
with (0).
You have skipped a lot of the basics of TMs.
TMs have to have a default/null character. You defined this
framework as having 0 as its blank/null/default character
and 1 as its only "data" character. This is a perfectly correct
TM alphabet but it makes a lot of things unnecessarily big and
complicated; in particular, the natural way of representing natural
numbers here requires n 1's to represent n. This also means that
EVERY FINITE s ends with (0). What it MEANS for a string to HAVE an end,
in this context, is to end with infinitely many 0s. All other strings are
infinitely long, i.e., they DON'T have an end. It is not possible to
have a finite s that does not end with (0). Just from this 1 premise and
your definition of S, it follows that x is an infinitely long string.
But that all by itself means that x is NOT A NATURAL NUMBER AT ALL,
let ALONE a "computable" number. Again, the basic problem is that
you still have NOT SAID what you MEAN by "number"! WHAT IS a number??
ANSWER THE QUESTION!
: > 2 x differs from every s with an inital segment not of the form
: 111.111.
Every string that starts with a 1 has an initial segment that IS of
the form 111...111. The only way to differ from every string that
does not start with a 1 is to start with a 1. So all you are saying
here is that x starts with a 1. That is trivial; you could've just
said that.
: > 3 x differs from every s with form 111...111(0).
Only if TM that produced it ran forever, in which case that
TM never finished producing ANYthing. To say this is to say
fundamentally that x cannot exist.
: > 4 Therefore, x differs from every member of S.
Of course it does. x is infinite. Every member of S is finite.
: > Prove that x is a RM computable number.
x is NOT a NUMBER at ALL, dumbass! WHAT KIND of number MIGHT
it be, if it were???
: > OK 1-3 are the properties of x. but 3 seems blatently wrong.
:
: Line 3 is correct.
: x must differ from every string with form 111...111(0).
: Specificaly, x has more initial 1's than any string like this in S.
: And x has a finite number of 1's.
BUT *YOU* *DEFINED* S as containing EVERY string that was the output
of a *TM* that wrote a finite number of 1s and then stopped with an 0!
That means S contains EVERY string with a finite number of 1's! So x
CANNOT contain "more initial 1's than any string in S", because
there IS NO UPPER LIMIT on the number of initial 1s on strings in S!
S is a collection of outputs from TURING machines! TURING machines
ALREADY have a definition from TURING! EASTERLY does NOT GET TO HAVE
AN OPINION on what their outputs might be!
: Saying x has an infinite number of 1's is overkill.
: I only need to show that x is longer than any string in S.
But it ISN'T. NOTHING is "longer than any string in S"!
The strings in S have NO upper bound on their length!
They include ALL finite strings of 1's! WHAT PART OF *ALL* don't
YOU understand, since YOU wrote the definition, DUMBASS???????
: I don't have to assume x has infinite length.
Yes, actually, you do.
: x is exactly one 1 longer than some finite string of 1's in S.
Then x is in S.
There is no longest string in S. For every s in S, the string
exactly one 1 longer than s IS ALSO IN S.
: x must have a finite string of 1's.
No, it must not.
: x represents a relatively "small" natural number.
x represents no natural number at all, dumbass.
You still have not even said what numbers are represented
by strings of any form other than a finite nummber of 1's
followed by all 0's.
: For example, x=RM(i) and i >> |x|.
Maybe RMs are just more powerful than TMs, simply because they
can run forever and yet still give well-defined results.
You should never have invented RMs at all, frankly.
If you had just stuck to TMs, it would be easy to unconfuse you.
: Are you sure you want me to post x?
You CANNOT post x, dumbass.
: > You've proven that x is different to ONE member of the list.
:
: x differs from every member of S.
: See above.
Then x does not exist. Every finite string of ones IS IN S, fool.
: The proof shows that it is impossible for a TM to count to infinity.
That is true BY DEFINITION OF TM, fool.
It does NOT NEED a proof! The reason why TM's can't count to infinity
is that TMs HAVE TO HALT, after a FINITE amount of time, in order to
be counted as having FINISHED producing their result!
: Imagine a TM that counts how many tapes it has read.
: Even if this TM reads an "infinite" number of tapes,
: the TM will tell us it has read a finite number.
: Similarly, a TM will say that the length of any tape is finite.
No, it won't.
The only way a TM can say anything is by halting.
WHAT it says is (conventionally) determined by the contents of its output tape
at the time. Since the output tape is the input tape, if the input tape
was originally infinite, it will still be infinite after the TM halts
and so the TM will still "say" that.
-- --- "It's difficult ... you need to be united to have any strength, but internal issues have to be addressed." --- E. Ray Lewis, on liberalism in America
- Next message: Arthur J. O'Dwyer: "Re: Cardinality of Set of Computable Numbers?"
- Previous message: George Greene: "Re: Cardinality of Set of Computable Numbers?"
- In reply to: Russell Easterly: "Re: Cardinality of Set of Computable Numbers?"
- Next in thread: George Greene: "Re: Cardinality of Set of Computable Numbers?"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
