Re: Most Natural Numbers Are Uncomputable

On 2009-07-26 23:06:47 -0400, Tim Little <tim@xxxxxxxxxxxxxxxxxx> said:

On 2009-07-26, RussellE <reasterly@xxxxxxxxx> wrote:

and therefore BNTM will "eventually" write every finite string of
1's.

It does write every finite string of 1's. It just does not write an
infinite string of 1's.

It's probably worth pointing out[0] that there is no natural number n where, at the n'th step, the BNTM has written all finite strings of 1s. It's only in the limit, after more than finitely many steps, that it "has written" more than finitely many finite strings of 1s, and can therefore "have written" N.

The quotes are there because the behaviour after infinite number of iterations cannot be used to draw random conclusions about the behaviour after finite numbers of iterations.

One of the benefits of describing systems like Turing machines in terms of functions on sets is that you can do away with the sort of verbal ambiguity that comes from ad-hoc descriptions. In particular, it's very easy to demonstrate that, for a system containing

f_0 = ""
f_n = f_(n - 1) + "1"
|f_n| = n [read |x| as 'length of x' here -oj]

that, if n is a natural number, then no f_n contains infinitely many 1s, and that every natural number of 1s has a corresponding f_n. We can, with effort, formally prove that

Ax Ey |f_y| > x

is true, and that

Ey Ax |f_y| > x

is false for x and y as natural numbers. In fact, we can strip this down even further:

Ax Ey y > x

is true, and

Ey Ax y > x

is false so long as x and y are natural numbers. Similarly, if we admit values of n in f_n that are not natural numbers, then we can prove different, interesting things, including that

Ax |f_omega| > x

where x is a natural number.

When you get to even this minimal level of formalism, RusselE's "contradiction" evaporates like a bad dream: by moving from *apparent* precision, framed in words like "eventually" and "writes" to *formal* precision, framed in terms of structured sequences of symbols, Russel's non-sequiter "contradiction" is shown for the broken argument it is.

Words are *not* enough.

-o

[0] To Russel and those like him, *again*, because it surely hasn't stuck yet...

.

Relevant Pages

  • Re: infinity
    ... An infinite range of values ... For sequences, like the naturals, unbounded implies ... >> finite set of finite strings that can contain all finite strings? ... >> If an axiom system is self-contradictory in isolation, ...
    (sci.math)
  • Re: Cantorian pseudomathematics
    ... >>> That's a theorem of set theory already. ... >> finite strings on a finite alphabet to be infinite? ... > Because the set of all finite strings on a finite alphabet is not ...
    (sci.math)
  • Re: infinity
    ... An infinite range of values ... Unworkable definition, since, for example, the set of natural naturals ... finite set of finite strings that can contain all finite strings? ... >> That is stuff of your imagination and not covered by the axioms, ...
    (sci.math)
  • Re: infinity
    ... > Tony Orlow wrote: ... The sum of all finite strings IS the size of the set. ... size is infinite or not. ...
    (sci.math)
  • Re: new standard for Euclid IP proof-- able to give both Direct and Indirect alongside one a
    ... By contradiction: ... Mark I can understand now why you like the Wikipedia entry even though ... cardinality increase from any finite cardinality ... *any* finite set is increased in cardinality implies it is infinite. ...
    (sci.math)