"Russell Easterly" <logiclab@comcast.net> wrote in
news:q8CdnfPGJ8E4knOiRVn-tw@comcast.com:


I give a constructive method of creating a RM computable number, x,
that is not in S. How can my method fail to produce x?

Because every x would be of the form (0)11..1, and because of the
definition of S, any such RM number is contained in S.

You assume that every string that corresponds to a finite number is in
S. This is not true if my proof is correct.

That was how S was defined : it contains all the strings of the form
(0)11..1 (this can be considered as all unary representations of natural
numbers).

I can only think of two reasons why I would not be able to compute x.

1) S contains a member with infinitely many 1's
2) S contains a member with so many 1's that adding
one more 1 results in an infinitely long string of 1's.

If you can think of another reason why x can not be computed,
please post it.

3) for any s in S, s-with-a-1-added-to-the-back is also contained in S

Can you show that x is impossible to compute?

As there can not exist an element which is both member of a set and not
contained in the set, yes.

RM's are a subset of TMs.
Any RM can be emulated by a universal Turing machine (UTM).
We are only concerned with the subset of RM's that output an initial,
finite and contiguous string of 1's followed by an infinite string of 0's.

and then prove that it is not in my list.

0.000...
0.1000...
0.11000...
0.111000...
0.1111000...
0.11111000...
0.111111000...
...

Good luck trying to prove the diagonal number is
not in the list using a countable number of operations.

Seems too easy, surely? If I understand you correctly the "diagonal
number" is:

0.11111....

Every number in your list consists of a finite string of 1s followed
by zeros ("000..."). The diagonal number doesn't. Ergo it isn't in the
list.

0.111000...
0.1111000...
0.11111000...
0.111111000...
^--------

"Barb Knox" <see@sig.below> wrote...
[ Obviously, every natural number N is computable by an N-state FSM. ]
So in what sense isn't every natural number computable?

Consider all TM's that write an initial, finite and contiguous strings of
1's and then halt. Let S be the set of all output tapes from these TM's.

Define another TM I call a comparator (CTM).
CTM compares the input tape to its output tape.
If the input tape has more 1's, the CTM rewinds
to the beginning of its output tape, copies the input tape,
and then writes an additional 1 to the end of the output.

We let CTM read all the tapes in S.

What is on the output tape of CTS?

The output of CTM must have a finite number of 1's.
Every tape read by CTM was finite in length.
The output of CTM has exactly one more 1 than
some input tape in S.

S can not contain every possible string that
represents a natural number.

"Daniel W. Johnson" <panoptes@iquest.net> wrote...
Russell Easterly <logiclab@comcast.net> wrote:

Let R be the set of all rational numbers, r, such that 0 <= r < 1.
If R can be ordered such that the diagonal is a rational number,
the diagonal proof shows the rationals to be uncountable.

And if my grandmother had wheels, she'd be a wagon.

There are several ways to put that subset of the rational numbers into
one-to-one correspondence with the positive integers.

Here is an example of the beginning of a complete list:

0
1/2
1/3
2/3
1/4
3/4
1/5
...

Identifying a rational given its position (or vice-versa) is probably
going to require generating the list up to that position, but this list
is obviously complete. Therefore, the set of rational numbers in [0,1)
is countable.

Maybe. That is the point of the proof.

How are you proving your list is complete?

To prove that the set contains all rational numbers
you will have to show there is no way to order
the set such that the diagonal is rational.
There are a lot of ways to order a set of rationals.

You want a proof that any such complete list has an irrational diagonal?
Okay:

Assume that a complete list with a rational diagonal can be found. The
diagonalization process would generated a rational number not in the
list. This would contradict the assumption. Therefore, either the list
is incomplete or the diagonal is not rational.

"Russell Easterly" <logiclab@comcast.net> wrote in
news:Bu-dnYP-tIz1JHOiRVn-sA@comcast.com:


OK, consider the set of natural numbers, N.
Also consider the operation "+ 1".

Is it not true that for each n in N, n + 1 is also in N ?

Now, consider the function f : N -> RM-numbers :

f(0) = (0)
f(1) = (0)1
f(2) = (0)11
...
and so on, with f(n) corresponding to its own RM-number for each natural
number n.

Clearly, not all the different RM-numbers are reached by this function f.
Consider the set F = f(N) of numbers which are. For each element s of F,
we
can find a unique natural number n such that s = f(n). This means we can
give the inverse function of f, call this g.
Now, for each s in F, there can not be an x which is s followed by an
extra
1, which is not already in F : this would mean that g(x)=g(s)+1, with g(s)
a natural number, would not be a natural number.

----------------------------- <^> <(·¿·)
^> -----------------------------

"Russell Easterly" <logiclab@comcast.net> wrote in

RM's are a subset of TMs.
Any RM can be emulated by a universal Turing machine (UTM).
We are only concerned with the subset of RM's that output an initial,
finite and contiguous string of 1's followed by an infinite string of
0's.


So you're not proving there is no complete RM list, 1st you are
proving there is no complete restricted RM list?

Is this based on modelling the diagonal number from your previous post?

quote

and then prove that it is not in my list.

0.000...
0.1000...
0.11000...
0.111000...
0.1111000...
0.11111000...
0.111111000...
...

Good luck trying to prove the diagonal number is
not in the list using a countable number of operations.

Seems too easy, surely? If I understand you correctly the "diagonal
number" is:

0.11111....

"Pento" <robby.goetschalckx@student.kuleuven.ac.be.NOSPAM> wrote in message
news:Xns945F820BCBD74robbygoetschalckxstu@134.58.127.12...
"Russell Easterly" <logiclab@comcast.net> wrote in
news:Bu-dnYP-tIz1JHOiRVn-sA@comcast.com:


OK, consider the set of natural numbers, N.
Also consider the operation "+ 1".

Is it not true that for each n in N, n + 1 is also in N ?

Maybe.
I might not be the person you want to ask this question to.
My proof shows that no set can contain every computable
natural number. If N does not contain every computable
natural number, how can we say N contains all natural numbers?

In article <19idnd3Ywuot6HKiRVn-sA@comcast.com>,
"Russell Easterly" <logiclab@comcast.net> wrote:

"Pento" <robby.goetschalckx@student.kuleuven.ac.be.NOSPAM> wrote in
message
news:Xns945F820BCBD74robbygoetschalckxstu@134.58.127.12...
"Russell Easterly" <logiclab@comcast.net> wrote in
news:Bu-dnYP-tIz1JHOiRVn-sA@comcast.com:


OK, consider the set of natural numbers, N.
Also consider the operation "+ 1".

Is it not true that for each n in N, n + 1 is also in N ?

Maybe.
I might not be the person you want to ask this question to.
My proof shows that no set can contain every computable
natural number. If N does not contain every computable
natural number, how can we say N contains all natural numbers?

(I haven't been following this thread, so please make allowances if what
I say here is either redundant or irrelevant.)

The standard definitions of "computable" are equivalent to "computable
by some Turing machine". Now clearly, each particular natural number K
can be generated by some TM; indeed, it's even computable by a
finite-state machine (with K states).

Furthermore, the infinite sequence of all natural numbers together
(e.g., in base 1, 010110111011110111110...) can be generated by a
(non-halting) TM -- the algorithm repeatedly copies the last string of
1's (which can be done finitely by temporarily replacing the most recent
1 copied with some other symbol, to keep track of how much has already
been copied) and writes an extra 1.

So in what sense isn't every natural number computable?

Let R be the set of all rational numbers, r, such that 0 <= r < 1.
If R can be ordered such that the diagonal is a rational number,
the diagonal proof shows the rationals to be uncountable.

Most people will argue that the diagonal of this set must be
an irrational number. I have never seen a proof of this.
It is easy to come up with a list of rationals that have a rational
diagonal. The set I give above is one such set.

RM's are a subset of TMs.
Any RM can be emulated by a universal Turing machine (UTM).
We are only concerned with the subset of RM's that output an initial,
finite and contiguous string of 1's followed by an infinite string of
0's.


So you're not proving there is no complete RM list, 1st you are
proving there is no complete restricted RM list?

This is the only subset of RM's anyone has concerns about.
I think everyone agrees my method works for all the other RMs.

Is this based on modelling the diagonal number from your previous post?

Partly.

quote

and then prove that it is not in my list.

0.000...
0.1000...
0.11000...
0.111000...
0.1111000...
0.11111000...
0.111111000...
...

Good luck trying to prove the diagonal number is
not in the list using a countable number of operations.

Seems too easy, surely? If I understand you correctly the "diagonal
number" is:

0.11111....

The diagonal method can be converted into the computable number proof.

Of course, when I responded to your thread I was arguing against Cantor's
diagonal proof. I am arguing for it in this thread.

Forcing the diagonal number to be computable shows that invoking
infinity is like killing a fly with a machine gun.

All we really need to prove it that the diagonal has more 1's than
any of the real numbers in the list above. The diagonal can have
a finite number of 1's and still not be in the list.

I suspect that the diagonal proof can be modified to show that
the rational numbers are uncountable.

Let R be the set of all rational numbers, r, such that 0 <= r < 1.
If R can be ordered such that the diagonal is a rational number,
the diagonal proof shows the rationals to be uncountable.

Most people will argue that the diagonal of this set must be
an irrational number. I have never seen a proof of this.

It is easy to come up with a list of rationals that have a rational
diagonal. The set I give above is one such set.


Russell
- 2 many 2 count

In article <19idnd3Ywuot6HKiRVn-sA@comcast.com>,
"Russell Easterly" <logiclab@comcast.net> wrote:

"Pento" <robby.goetschalckx@student.kuleuven.ac.be.NOSPAM> wrote in message
news:Xns945F820BCBD74robbygoetschalckxstu@134.58.127.12...
"Russell Easterly" <logiclab@comcast.net> wrote in
news:Bu-dnYP-tIz1JHOiRVn-sA@comcast.com:


OK, consider the set of natural numbers, N.
Also consider the operation "+ 1".

Is it not true that for each n in N, n + 1 is also in N ?

Maybe.
I might not be the person you want to ask this question to.
My proof shows that no set can contain every computable
natural number. If N does not contain every computable
natural number, how can we say N contains all natural numbers?

(I haven't been following this thread, so please make allowances if what
I say here is either redundant or irrelevant.)

The standard definitions of "computable" are equivalent to "computable
by some Turing machine". Now clearly, each particular natural number K
can be generated by some TM; indeed, it's even computable by a
finite-state machine (with K states).

Furthermore, the infinite sequence of all natural numbers together
(e.g., in base 1, 010110111011110111110...) can be generated by a
(non-halting) TM -- the algorithm repeatedly copies the last string of
1's (which can be done finitely by temporarily replacing the most recent
1 copied with some other symbol, to keep track of how much has already
been copied) and writes an extra 1.

So in what sense isn't every natural number computable?

Russell Easterly <logiclab@comcast.net> wrote:

Let R be the set of all rational numbers, r, such that 0 <= r < 1.
If R can be ordered such that the diagonal is a rational number,
the diagonal proof shows the rationals to be uncountable.

And if my grandmother had wheels, she'd be a wagon.

There are several ways to put that subset of the rational numbers into
one-to-one correspondence with the positive integers.

Most people will argue that the diagonal of this set must be
an irrational number. I have never seen a proof of this.
It is easy to come up with a list of rationals that have a rational
diagonal. The set I give above is one such set.

Of course, that set was not all of the rationals in that range.

Here is an example of the beginning of a complete list:

0
1/2
1/3
2/3
1/4
3/4
1/5
2/5
3/5
4/5
1/6
5/6
1/7
...

Identifying a rational given its position (or vice-versa) is probably
going to require generating the list up to that position, but this list
is obviously complete. Therefore, the set of rational numbers in [0,1)
is countable.

You want a proof that any such complete list has an irrational diagonal?
Okay:

Assume that a complete list with a rational diagonal can be found. The
diagonalization process would generated a rational number not in the
list. This would contradict the assumption. Therefore, either the list
is incomplete or the diagonal is not rational. (My list is complete, so
the diagonal must not be rational. Your list had a rational diagonal,
but was obviously incomplete.)

"Russell Easterly" <logiclab@comcast.net> writes:
: Let S be the set of all computable numbers
: and assume S is countable.

I have made the proof a little more rigorous.

First, I define how to "compute" a computable number.
I do this with a very non-standard type of Turing machine.
Let's call these "Russell machines" (RM).
A number is computable if it can be represented by
the infinite binary string produced by a RM. [...]

In article <-sOdnVAq4PkNeXGiRVn-sA@comcast.com>,
"Russell Easterly" <logiclab@comcast.net> wrote:

"Russell Easterly" <logiclab@comcast.net> writes:
: Let S be the set of all computable numbers
: and assume S is countable.

I have made the proof a little more rigorous.

First, I define how to "compute" a computable number.
I do this with a very non-standard type of Turing machine.
Let's call these "Russell machines" (RM).
A number is computable if it can be represented by
the infinite binary string produced by a RM. [...]

Let C be the set of all RM-computable binary strings, according to your
definition. To show that C is countable, it suffices to demonstrate a
one-to-one function f : C -> N, where N is the set of natural numbers {
0, 1, 2, ... }. This is not difficult.

So: We can now define a one-to-one function f : C -> N as follows:

f(c) := E(M(c))

Quickly, let's argue that this is one-to-one: Let c1 and c2 be
RM-computable strings with c1 <> c2. Then M(c1) <> M(c2)**, and by the
definition of E, E(M(c1)) <> E(M(c2)), so we're all set.

How are you proving your list is complete?

To prove that the set contains all rational numbers
you will have to show there is no way to order
the set such that the diagonal is rational.

There are a lot of ways to order a set of rationals.