1. Natural
    0, 1, 2, 3, 4, 5 … …
  2. Rational
    m/n
  3. Irrational
    the formula:    a*a+b*b=c*c;
    some are computable(countable? enumerable?), for example pi and e(there exists a program which can display each its number)
    most are not, see the "Cantor’s diagonal argument"

ref:

  1. http://www.i-programmer.info/babbages-bag/1902-non-computable-numbers.html
  2. http://en.wikipedia.org/wiki/Cantor’s_diagonal_argument

Question:

  1. ref1 states that "All I have to do is write a for loop that counts from 1 to 2^N and I have all the programs that can be stored in N bits.Even if you let this process go to infinity the number of programs is enumerable"
    Does it imply that the sequence of 0/1 string(set T in ref2, I believe) is countable?
  2. But ref2 states that " Thus T is uncountable: it cannot be placed in one-to-one correspondence with the set of natural numbers \mathbb{N}."
    Does it imply that set T is not countable?
  3. If answers of q1 and q2 are yes, and enumerable = countable, then the statements are contradict.

Answer:

  1. Personally, I do not agree what ref1 states if enumerable=countable(This article was not written precisely). ref2’s proof is precise(There is no formal definition for enumerable number or countable number, but there does exist formal definition for countable set http://en.wikipedia.org/wiki/Countable_set)
    "The point is that you can’t enumerate a sequence of infinite sequences." programs are such sequences.
    "Any program is simply a sequence of bits so the set of programs is enumerable." programs are enumerable??
  2. Or countable is not identical to computable.
  3. What is computable number?
    http://en.wikipedia.org/wiki/Computable_number

Note:

  1. What does ref1 want to say?
    Naturals are computable.
    Ratinals are computable.
    Some Irrationals are computable. Vast majority of irrationals are not computable.
  2. There are 2 concepts here:
    is a number computable?
    Is a set of specific numbers enumerable(countable)?
    Ref1 discussed both, but readers must differentiate them.
  3. Ref1 used Cantor’s diagonal argument to demonstrate the set of irrationals is not countable, then it started to infer that vast majority of irrationals are not computable. So my question is how this conclusion be decided by him? Is there any connection between a set’s countability and its member’s computability?
    Assuming these 2 points:
    there is 1 vs 1 relationship between each program and each irrational number(Yes, one program can only display at most one infinite number)
    programs are finite(Yes, this is true)
    We can come to the conclusion that some irrational numbers are not computable. And since infinite is always bigger than finite programs, we can come to conclusion that vast majority of irrational numbers are not computable.

Personal Conclusions:

  1. Set is Countable = Bijection between the Natural Number set and this set
    集合S是可数的,如果在S和自然数集之间存在双射
  2. Reals(the number of reals) is not countable
  3. 无限长的0|1序列构成集合P,集合P是uncountable,见Cantor的证明
  4. Infinite and Finite programs
    Infinite programs are not countable.(Does there exist an infinite program? NO, at least now programs can not be infinite. )
    Finite programs are countable.(Bullshit!Anything definite is countable)
  5. There exists non-computable numbers.
    存在着无限的数字;数字的集合是无限的
    有限的数字是可计算的;不可计算的数字一定是无限的
    1个程序至多能计算出有限个无限数字(how to prove it?)
    因为程序的集合时有限的,所以所有的程序计算出的数字集合也是有限的
    得出结论,存在着无法计算的数字
  6. when we are talking about computable,we must introduce Turing Machine。
Advertisements