« first day (245 days earlier)      last day (154 days later) » 

Simply Beautiful Art
Simply Beautiful Art
00:02
Further expansions:
H(ε_0^(ω+1)(ω+1)+ε_0^(ω+1),2)
= H(ε_0^(ω+1)(ω+1)+(ε_0^ω)ε_0,2)
= H(ε_0^(ω+1)(ω+1)+(ε_0^ω)(ω^ω),2)
= H(ε_0^(ω+1)(ω+1)+(ε_0^ω)(ω^2),2)
= H(ε_0^(ω+1)(ω+1)+(ε_0^ω)(ω2),2)
= H(ε_0^(ω+1)(ω+1)+(ε_0^ω)(ω+2),2)
= H(ε_0^(ω+1)(ω+1)+(ε_0^ω)(ω+1)+ε_0^2,2)
= H(ε_0^(ω+1)(ω+1)+(ε_0^ω)(ω+1)+(ε_0)(ω^ω),2)
= H(ε_0^(ω+1)(ω+1)+(ε_0^ω)(ω+1)+(ε_0)(ω^2),2)
= H(ε_0^(ω+1)(ω+1)+(ε_0^ω)(ω+1)+(ε_0)(ω2),2)
= H(ε_0^(ω+1)(ω+1)+(ε_0^ω)(ω+1)+(ε_0)(ω+2),2)
= H(ε_0^(ω+1)(ω+1)+(ε_0^ω)(ω+1)+(ε_0)(ω+1)+ω^ω,2)
= ...
 
1 hour later…
Simply Beautiful Art
Simply Beautiful Art
01:02
Hm, why is @user202729 in here? :P Head back to bed?
user202729
user202729
Why shouldn't I?
One question: How is countable/uncountable ordinal defined?
Simply Beautiful Art
Simply Beautiful Art
For some reason I thought you had headed into bed.
@user202729 through bijection
You would like me to explain that?
user202729
user202729
Yes.
But I have to go for a short time now
Simply Beautiful Art
Simply Beautiful Art
lol
It comes down to whether or not you can name all of the ordinals less than x using the natural numbers.
Take ω. Clearly it is countable because all of the ordinals less than it are natural numbers.
ω+1 is also countable because I can describe it as:
{0, 1, 2, 3, 4, ..., ω}
And I can assign values to this as
{1, 2, 3, 4, 5, ..., 0}
That is, I can match each natural number to exactly one ordinal less than ω+1, and every ordinal less than ω+1 matches with one natural number.
Here,
0 matches with 1,
1 matches with 2,
2 matches with 3,
etc.,
ω matches with 0.
ω∙2 is countable because
{0, 1, 2, 3, 4, ..., ω, ω+1, ω+2, ω+3, ...}
matches up as
{0, 2, 4, 6, 8, ..., 1, 3, 5, 7, ...}
In fact, every ordinal I've mentioned is countable.
The reason being is that recursive operations will always keep things countable.
But there is an ordinal ω_1 so large that all of the ordinals less than it cannot be matched up with the natural numbers.
user202729
user202729
Ok
Simply Beautiful Art
Simply Beautiful Art
01:16
Before you reach ω_1, you'll actually reach ω_1^CK, the Church-Kleene ordinal, which is the first ordinal so large that it cannot be encoded into a program. It is 'uncomputable'.
ω_2 is then the first ordinal larger than ω_1 and has no bijection to smaller ordinals.
and so on.
You can prove that ω_1 must exist, since there is a set (the set of all real numbers) which is uncountable.
Any other questions/clarifications?
user202729
user202729
So I'm reading recursive ordinal
and I may ask if have any more question.
Simply Beautiful Art
Simply Beautiful Art
okie dokie.
In a sense, uncomputable ordinals are nice for a thing called 'ordinal collapsing functions'. Usually one takes the path of using uncountable ordinals, but you quickly reach a point where you can't prove 'so and so' ordinal even exists anymore! With uncomputable ordinals, it is much easier to prove their existence.
user202729
user202729
So... what is a recursive ordinal/well-ordering? (from this definition of recursive ordinal)
Simply Beautiful Art
Simply Beautiful Art
It's best to look back at the explanation that ω∙2 is countable
14 mins ago, by Simply Beautiful Art
ω∙2 is countable because
{0, 1, 2, 3, 4, ..., ω, ω+1, ω+2, ω+3, ...}
matches up as
{0, 2, 4, 6, 8, ..., 1, 3, 5, 7, ...}
And ask yourself if a computer can partition the natural numbers as even or odd.
If a computer can do this, it is computable/recursive.
user202729
user202729
So recursive = computable?
Simply Beautiful Art
Simply Beautiful Art
01:27
Yes
Eventually you'll reach an ordinal that can be rewritten using the natural numbers like I did above, but too large for a theoretical Turing machine to understand it.
Once you've hit that point, you're past computable/recursive.
user202729
user202729
So... the set of all computable ordinal is not computable.
Simply Beautiful Art
Simply Beautiful Art
Nope.
:-) It's kinda like the halting problem.
@user202729 Also, how could the set of all computable ordinals be computable?
If it were computable, it would already be in the set... but its not!
Jun 26 at 16:55, by Nilknarf
user image
@Nilknarf you're missing all the good stuff
@user202729 Could you imagine trying to encode numbers this large with no background in using ordinals this way?
user202729
user202729
@SimplyBeautifulArt What is the computer exactly supposed to do?
In other words, if the computer can do ..., then the ordinal is countable?
Simply Beautiful Art
Simply Beautiful Art
If the computer can find a bijection from the natural numbers to the ordinal, then that ordinal is computable.
user202729
user202729
So, if the computer can take a natural number and output an ordinal number, the ordinal is computable?
I still find it weird that the computer can output an ordinal number. / in which encoding?
Simply Beautiful Art
Simply Beautiful Art
01:38
Wikipedia actually says we can simply use a subset of the natural numbers rather than all of the natural numbers.
@user202729 no
An ordinal is the set of all ordinals less than it.
If a computer can, for every ordinal less than x, output some unique natural number n, then x is computable.
user202729
user202729
How is the computer supposed to take an ordinal as input? In any encoding? As a Turing machine for computing that ordinal the same way?
Simply Beautiful Art
Simply Beautiful Art
Any encoding. You could use some sort of special notation, or take a string. Doesn't really matter.
For example, we could use ω∙2 again.
If you input a natural number, output double it.
If you input ω plus a natural number, double the natural number and add 1, then output.
 
22 hours later…
Simply Beautiful Art
Simply Beautiful Art
23:36
@user202729 @Mr.Xcoder Oops, minor mistake. 0 = ∅ = {}. However, everything else follow suit; this doesn't really make much of a difference.

« first day (245 days earlier)      last day (154 days later) »