Primes and Squares

wizzwizz4

08:32

I'm back. I'll wait for you to reappear.

fejfo

09:04

@wizzwizz4 Maybe I could help you while you wait, I don't know as much about ordinals but I should be able to explain "the basics" to you

wizzwizz4

That would be great! Thanks.

fejfo

What was he explaining to you?

wizzwizz4

TREE(3), I think.

fejfo

Was he explaining an approximation of TREE(3)? Because TREE(3) it self isn't about ordinals although they are really useful to understand/imagine how stupidly large TREE(3) is

wizzwizz4

@fejfo I think he was explaining actual TrREE(3) but I'm not sure.

fejfo

09:17

@wizzwizz4 This is a video about TREE(3) that's about all I know about the actual TREE function, but I will try to explain it myself if you don't have time to watch the video rigth now

wizzwizz4

Why does nobody call TREE(TREE(3)) a big number?

Or better, BB(TREE(3)).

fejfo

because big depends on what you compare it too, TREE(TREE(3)) is much much larger than TREE(3) or Graham's number

when you keep nesting fast growing functions you keep getting bigger an bigger numbers but they lose their "elegance", they aren't a these beautifully crafted functions anymore but just a random pile of functions

wizzwizz4

@fejfo That's a point.

fejfo

but yes BB(TREE(3)) > TREE(TREE(3))

wizzwizz4

We don't know whether BB(10) > TREE(3) as far as I know.

fejfo

09:26

No Idon't answering such a question is really difficult but BB >> TREE (BB eventually outgrows TREE, BB(n)>TREE(n) for all n>some value)

To answer questions like this people try to approximate these number is the fast growing hierarchy or the Hardy hierarchy. Sometimes these approximations are easier to understand, but knowing about them is always useful

flawr

FOREST(N) > TREE(N) > BUSH(N)

wizzwizz4

09:43

@flawr What's the FOREST function?

fejfo

@wizzwizz4 think it was a joke (I can't seem to find anything about the FOREST or BUSH function)

fejfo

10:21

@wizzwizz4 So, are you still here? Do you want me to continue to explain the a hierachy?

flawr

10:50

In graph theory there is actually the term forest, which is sometimes used for a certain "collection" of arborescences (directed/rooted trees), but yes it was not serious:)

fejfo

11:17

That makes me think could you define a forest function, FOREST(n)= the longest sequence of forest for which:
1) each forest is a TREE(n) like sequence of TREE's
2) Not all the trees in a previous forest can be embed-able in the trees of the following forest

Simply Beautiful Art

12:13

@wizzwizz4 Lol, I was asleep.

wizzwizz4

Why can't half the world be nocturnal? :-p

@SimplyBeautifulArt Time zones are irritating.

Why can't half the world be nocturnal? :-p

Simply Beautiful Art

@wizzwizz4 @fejfo There is an interesting point I'd like to make. Though TREE(TREE(3)) > TREE(4) > TREE(3), I wouldn't call them much larger, since they can all be represented using TREE(n).

@wizzwizz4 yeah

I call something larger if it can't be reasonably represented in terms of smaller things.

e.g. TREE(3) can't be represented using variations of Graham's number.

@fejfo I was still in the process of explaining how ordinals work.

wizzwizz4

@SimplyBeautifulArt In which case TREE(3) is no larger than 1.

fejfo

@SimplyBeautifulArt on the scale of these huge numbers they may not be much larger but If you think about how many more decimal digits it takes to represent TREE(TREE(3)) than TREE(3) the difference is pretty insane

Simply Beautiful Art

@wizzwizz4 ignoring trivial values.

@fejfo But what meaning does "difference" have?

See, for me, I imagine a graph.

wizzwizz4

12:18

Now that I am less tired I should be able to deal with ordinals.

My internet is still no better than it was.

Simply Beautiful Art

We start off with normal indexes on the axes, both scaling linearly.

You can imagine this to be a normal scaling we use to compare normal numbers.

Eventually, we get to much larger numbers like 10000000.
So the indexes count by, say, 1000000 at a time.

wizzwizz4

@SimplyBeautifulArt What are you going to use that /axe?/ for? :-p

Simply Beautiful Art

Eventually, the numbers get much bigger, so you can imagine we have to adjust our "scale" again to get a reasonable comparison between two numbers.

@wizzwizz4 axis (plural)

wizzwizz4

@SimplyBeautifulArt That makes sense.

Simply Beautiful Art

My point: By the time your y-axis counts in terms of TREE(n), TREE(TREE(3)) isn't "much bigger" than TREE(3).

Sure, its bigger, but its just one graph change up.

wizzwizz4

12:21

But TREE^2(n) >>>>>>>>>>>> TREE(n) for n>2.

fejfo

@SimplyBeautifulArt with difference I mean |a-b| but yes you can't really say much more than a>b because "much bigger", "a big difference", are subjective. I think your way of needing new notation works pretty well. But I saw a~=b <=> log(a)~=log(b) being used for large numbers a few times (because 3~=4 but 10^3<10^4)

Simply Beautiful Art

@fejfo yeah, kinda like that.

I suppose we shall get back to our ordinals?

fejfo

@SimplyBeautifulArt why are you explaining the TREE function in terms of ordinals? ordinals aren't required for the TREE right?

wizzwizz4

I understand what you mean, but I can't "picture" it.

The numbers are just too big.

Simply Beautiful Art

@fejfo No, but there are two reasons I'd prefer to explain it with ordinals. A) Ordinals provide a natural scale to compare TREE(n) with other crazy functions, and B) I don't fully understand TREE(n) as much as I'd like yet.

@wizzwizz4 I used to feel the same way, but ordinals really helped me compare things quickly.

@wizzwizz4 You feel comfortable with ω^2?

wizzwizz4

12:24

@SimplyBeautifulArt Ok then - back to ordinals. :-)

fejfo

I get that I have the same problem, but I don't like that your not actually explaining TREE(3) just a number on the order of TREE(3), but in any case learning about ordinals is really useful.

wizzwizz4

@SimplyBeautifulArt Yes.

Simply Beautiful Art

34

Q: How does Tree(3) grow to get so big? Need laymen explanation.

I am not a mathematician but I am interested in big numbers. I find them to be really interesting, almost god-like. I am watching a series of videos from David Metzler on youTube. I have a basic understanding of some fast growing functions. David does not cover Tree(n) which I've read is one ...

graph-theory

^ Explanation by smarter people of TREE(3) using ordinals

wizzwizz4

I can't submit messages on the first attempt.

Simply Beautiful Art

@wizzwizz4 :(

Googology.wikia ranks almost all of its computable functions using ordinals.

wizzwizz4

12:26

Or often the second.

Simply Beautiful Art

Okay, so last time we tried to define some rules as to how you simplify these ordinals.

17 hours ago, by Simply Beautiful Art

I usually use the following definition:

ω[n] = n

(a+b)[n] = a+(b[n])
(a∙b)[n] = a∙(b[n])
(a^b)[n] = a^(b[n])

a∙(b+1) = a∙b+a
a^(b+1) = (a^b)∙a

For example, we can expand H(3,ω^ω)

wizzwizz4

@SimplyBeautifulArt H(3,w^w) = H(3,w^(w[3]))

Simply Beautiful Art

Yup

wizzwizz4

H(3, w^3)

H(3, 3*w)

Simply Beautiful Art

Nope

fejfo

12:30

wait don't you mean H(w^w,3) = H(w^(w[3]),3) isn't the ordinal on the left?

Simply Beautiful Art

@fejfo shrugs don't think anyone really cares xD

@wizzwizz4 Hint: 3 = 2+1

wizzwizz4

w^3 = {0, w^2, 2*w^2 ...}?

Simply Beautiful Art

H(3,ω^ω)
= H(3,(ω^ω)[3])
= H(3,ω^(ω[3]))
= H(3,ω^3)
= H(3,ω^(2+1))
= H(3,(ω^2)∙ω)
= H(3,((ω^2)∙ω)[3])
= H(3,(ω^2)∙(ω[3]))
= H(3,(ω^2)∙3)
= H(3,(ω^2)∙(2+1))
= H(3,(ω^2)∙2+ω^2)
= H(3,(ω^2)∙2+ω∙ω)
= ...

Oops, that middle portion lol

wizzwizz4

Makes more sense now.

fejfo

...=H(3,ω²*2+ω*2+3)

Simply Beautiful Art

12:33

Fairly... straightforward.

Sooner or later you'll start skipping monotonous steps because there's a lot of pattern to exploit.

wizzwizz4

= H(3, (w^2)*2+w*3)

Simply Beautiful Art

@fejfo The last 2 should be a 3.

fejfo

You're rigth

Simply Beautiful Art

@fejfo :I Do you spell "right" like that everywhere on purpose?

wizzwizz4

= H(3, (w^2)*2+w*2+w)

Simply Beautiful Art

12:35

@wizzwizz4 yup

fejfo

@SimplyBeautifulArt I think I just can't spell

Simply Beautiful Art

@fejfo oh, fair enough

wizzwizz4

= H(3, (w^2)*2+w*2+w)

= H(3, (w^2)*2+w*2+3)

Simply Beautiful Art

Yup

wizzwizz4

= H(6, (w ^ 2)*2 + w*2)

Simply Beautiful Art

12:37

Yup.

A quick pattern to spot

Every ω doubles the first argument

wizzwizz4

= H(6, (w ^ 2) * 2 + w + 6)

= H(24, (w ^ 2) * 2 )

Simply Beautiful Art

Since there are two ω's, you could just double 6 twice to get
= H(24, (ω^2)∙2)

A fairly lengthy process.

Hopefully you realize that you aren't going to be able to explicitly write the final result in base 10.

wizzwizz4

= H(24, (w^2) + (w ^ 2))?

Simply Beautiful Art

Yup

wizzwizz4

@SimplyBeautifulArt Is this TREE(3)?

Simply Beautiful Art

12:40

@wizzwizz4 No

You'll probably have nightmares once you realize how large TREE(3) is.

So, I'm gonna cut you off and say the final result is...
H(3, ω^ω) = (24∙2^24)∙(2^(24∙2^24))

wizzwizz4

= H(24, (w^2) + w * w)

Simply Beautiful Art

Indeed, H(3, ω^ω) is smaller than a googolplex

@wizzwizz4 = H(24, ω^2 + ω∙24)

You can tell me when you're all good with this so far.

wizzwizz4

I understand this all now.

@SimplyBeautifulArt That's where the big comes from.

I can't communicate with you well though - too much laaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaag.

Simply Beautiful Art

Oh, did any of you guys see me recent question about the simplified Goodstein sequence?

fejfo

No, was it about the weak or the strong Goodstein sequence?

Simply Beautiful Art

12:47

Not sure if I mentioned this, but you can prove my sequence always goes to zero by representing the numbers in terms of ordinals. From there, you can even derive the closed form for how long it takes for my sequence to go to zero.

23

Q: Output the simplified Goodstein sequence

A number is in base-b simplified Goodstein form if it is written as b + b + ... + b + c, 0 < c ≤ b The simplified Goodstein sequence of a number starts with writing the number in base-1 simplified Goodstein form, then replacing all 1's with 2's and subtracting 1. Rewrite the result in base-2...

code-golf math sequence

@wizzwizz4 Think you are comfortable with expressions like ω^(ω^ω)?

wizzwizz4

...186 and ...189 are in the other order on my end because they went through in different orders to that I typed them.

@SimplyBeautifulArt Yes.

Simply Beautiful Art

Let's also establish the order of exponentiation while we're at it.

a^b^c = a^(b^c)

not (a^b)^c

So the next big ordinal is the first epsilon number, which transcends what you can write in basic stuff.

ε_0 = {1, ω, ω^ω, ω^ω^ω, ...}

wizzwizz4

Is w tetration n TREE(n)?

fejfo

I've to go now, bye

Simply Beautiful Art

@wizzwizz4 No, TREE(n) is much bigger ;)

@fejfo cya!

wizzwizz4

12:51

@SimplyBeautifulArt Couldn't you write it as ε_0_n = w tetration n?

o/

Simply Beautiful Art

For example,
H(3, ε_0)
= H(3, ω^ω^ω)
= H(3, ω^ω^3)
= ... really big...

@wizzwizz4 Tetration is ill-defined for ordinals. You'll run into a problem called "fixed-points"

Okay, so the problem with fixed-points begins here

Well, I actually hinted at it before

Recall that:
ω = {0,1,2,...}
1+ω = {1,2,3,...}

And in particular, ω = 1+ω

ω is the first number with the property x = 1+x

This is called a fixed-point.

If you have to reduce an expression such as
H(3,1+ω)

You need to reduce 1+ω into ω

i.e. H(3,1+ω) = H(3,ω)

That is, don't mess with the ordinals until they are fully simplified.

ε_0 is the first ordinal with the property x = ω^x

wizzwizz4

Are ordinals a subclass of both a set and an integer?

If it's a number, why is it also a set?

Simply Beautiful Art

@wizzwizz4 x'D Because set theory.

Practically everything is a set.

As fejfo mentioned before, you could have, say, 3 = {2, 2, 2, ...}

wizzwizz4

OIC.

Simply Beautiful Art

So there's some strange arithmetic that now arises.

wizzwizz4

12:58

So 0 = {-1, -1, -1...}

flawr

@SimplyBeautifulArt I object! :)

Simply Beautiful Art

@wizzwizz4 No, there is no such thing as negative numbers.

ω^(ε_0+1) = (ω^(ε_0))∙ω = (ε_0)∙ω

@wizzwizz4 The simplest thing is the empty set.

flawr

@SimplyBeautifulArt tell that my bank

Simply Beautiful Art

@flawr x'D

∅ = {} = empty set.
0 = {∅}
1 = {0}
etc.

flawr

so ∞ = {∞}?

Simply Beautiful Art

13:01

@flawr No, there is no "∞"

There is an ω = {0,1,2,3,...}

wizzwizz4

@flawr \aleph_0 = {\aleph_0} is your question, correct?

Simply Beautiful Art

and ω+1 = {ω}

Anyways, back to ε_0?

4 mins ago, by Simply Beautiful Art

ω^(ε_0+1) = (ω^(ε_0))∙ω = (ε_0)∙ω

^ Always simplify as much as possible first

wizzwizz4

ω = {{{}}, {{{}}}, {{{{}}}}, {{{{{}}}}}, {{{{{{}}}}}}, {{{{{{{}}}}}}}, {{{{{{{{}}}}}}}}...}?

Simply Beautiful Art

@wizzwizz4 Yup.

wizzwizz4

@SimplyBeautifulArt Is {{}} = {{}, {}...}?

Simply Beautiful Art

13:05

@wizzwizz4 Yeah

Okay, so do you think you can reduce ordinals involving ε_0?

Also, does anyone in here know Peano Arithmetic (PA)?

wizzwizz4

@SimplyBeautifulArt So does the ordering matter?

How is the ordering determined?

Simply Beautiful Art

What do you mean?

wizzwizz4

Do I sound like a 2 year old (i.e. my attitude to asking questions)?

Simply Beautiful Art

Lol, you're fine.

The ordering only matters when you want to do things like ω[n]

wizzwizz4

@SimplyBeautifulArt Is {{{}}, {{{{}}}}, {{{}}}, {{{{{}}}}}, {{{{{{}}}}}}, {{{{{{{}}}}}}}...} = ω?

@SimplyBeautifulArt I understand.

Simply Beautiful Art

13:10

@wizzwizz4 yes.

Okay, so the next "big" ordinal is ε_1.

ε_1 = {1, ε_0, ε_0^ε_0, ...}

ε_2 = {1, ε_1, ε_1^ε_1, ...}

etc.

wizzwizz4

Because of my lag, it'ss putting all of your pings into my main inbox. I might submit a bug.

Simply Beautiful Art

ε_ω = {ε_0, ε_1, ε_2, ...}

Lol, okay

Can you figure out what ε_(ω+1) is?

Oh, as a side note, you might be interested in looking at the leaderboard on Largest Number Printable. Over there, f_a(n) = H(n,ω^a)

:D Hopefully you can comprehend how massively insane the largest two numbers are.

wizzwizz4

@SimplyBeautifulArt {1, ε_1^ε_1, ε_2^ε_2...}?

Simply Beautiful Art

@wizzwizz4 Nope.

{1, ε_ω, ε_ω^ε_ω, ...}

ε_(ω+2) = {1, ε_(ω+1), ε_(ω+1)^ε_(ω+1), ...}

etc.

ε_(ε_0) = {ε_1, ε_ω, ε_(ω^ω), ...}

wizzwizz4

@SimplyBeautifulArt Why is ε_(w+1)[0] smaller than ε_w[0]?

Simply Beautiful Art

13:19

@wizzwizz4 Because ε_(a+1)[0] = 1 always (here), while ε_({a, b, c, ...})[0] = ε_a

wizzwizz4

Ok.

Simply Beautiful Art

So that's the general rule. We have
ε_0[0] = 1
ε_0[n+1] = ω^(ε_0[n])
ε_(a+1)[0] = 1
ε_(a+1)[n+1] = ε_a^(ε_(a+1)[n])
ε_({a1, a2, a3, ...})[n] = ε_an

The next big step is ζ_0

ζ_0 = {0, ε_0, ε_(ε_0), ε_(ε_(ε_0)), ...}

We also have ε_(ζ_0) = ζ_0

ε_(ζ_0+1)
= {1, ε_(ζ_0), ε_(ζ_0)^ε_(ζ_0), ...}
= {1, ζ_0, ζ_0^ζ_0, ...}

So that's what happens when you get an infinite tower of ζ_0's.

And this is still smaller than TREE(n).

ζ_1 = {ζ_0+1, ε_(ζ_0+1), ε_(ε_(ζ_0+1)), ...}

Note that we use ζ_0+1 to avoid having ε_(ζ_0) in the next step. You don't want ε_(ζ_0) because that is equivalent to ζ_0, which isn't any bigger.

ζ_2 = {ζ_1+1, ε_(ζ_1+1), ε_(ε_(ζ_1+1)), ...}

wizzwizz4

Given the sequence ??? = {0, w, E, Z...} is TREE(n) = H(n, ???[n][n])

Simply Beautiful Art

ζ_3 = {ζ_2+1, ε_(ζ_2+1), ε_(ε_(ζ_2+1)), ...}
etc.

wizzwizz4

Approximately how much bigger is TREE?

I had a layer of abstractation that let me deal with this, but I'm going to need to make another one.

Simply Beautiful Art

13:29

@wizzwizz4 nope, its way bigger

@wizzwizz4 Just wait a bit longer :-)

@wizzwizz4 Okay, so you've got the right idea there.

What we want to do is make a generalized function

This is called the Veblen function (φ)

φ_1(x) = ε_x
φ_2(x) = ζ_x
φ_3(x) = (recursion of φ_2(x))
etc.

wizzwizz4

I've just... I can't comprehend this.

How long ago did we exceed the number of plank-length-sized cubes that can fit inside the observable universe?

Simply Beautiful Art

@wizzwizz4 Since ω^4.

:-)

wizzwizz4

@SimplyBeautifulArt Oh.

Simply Beautiful Art

Possibly ω^3

φ_ω(0) = {φ_0(0), φ_1(0), φ_2(0), ...}
φ_ω(1) = {φ_0(φ_ω(0)+1), φ_1(φ_ω(0)+1), φ_2(φ_ω(0)+1), ...}
φ_ω(2) = {φ_0(φ_ω(1)+1), φ_1(φ_ω(1)+1), φ_2(φ_ω(1)+1), ...}
...

φ_ω(x) does recursion over φ_n(x) for every n<ω

wizzwizz4

How long ago did we exceed hyperoperations?

Simply Beautiful Art

13:35

@wizzwizz4 The kth hyperoperation is approximately equal to H(n,ω^k)

Graham's number is approximately H(64,ω^(ω+1))

φ_(ω+1)(x) does recursion over φ_ω(x)

etc.

wizzwizz4

I'm starting to get an actual headache. :-)

Simply Beautiful Art

@wizzwizz4 I got a headache the first time I went through all of this too xD

Let's just say that φ_a(b) = φ(a,b)

And φ(a,b,c) does recursions over φ(a,b)

and φ(a,b,c,d) does recursions over φ(a,b,c)

etc.

wizzwizz4

... Is the Veblen function computable?

Simply Beautiful Art

@wizzwizz4 yes

wizzwizz4

(Please say no, please say no.)

Simply Beautiful Art

13:39

φ(1,0,0,0,....) = {φ(1,0), φ(1,0,0), φ(1,0,0,0), ...}

wizzwizz4

I am beginning to understand why BB(5) is so hard.

Simply Beautiful Art

And then you can imagine repeating all this recursion over and over.

TREE(n) is at the level of φ(ω,0,0,0,....)+1

Or rather, we believe that TREE(n) is not much greater than or less than that.

wizzwizz4

So, TREE(n) ~= H(n, φ(ω,0,0,0,....)+1)?

Simply Beautiful Art

Oh, no, sorry, TREE(n) ~= f_(φ(ω,0,0,0,....)+1)(n)

where f_a(n) = H(n,ω^a)

So a tad bit larger.

wizzwizz4

And BB(n) >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> TREE^{TREE(n)}(n)...

Simply Beautiful Art

13:42

BB(n) is uncomputable.

Ordinal hierarchies are always computable.

ASCII-only

@wizzwizz4 .-. how can you throw comparisons around so easily

wizzwizz4

Now I'm starting to understand what uncomputable means.

Simply Beautiful Art

So no matter how large of an ordinal you make, BB(n) will eventually grow faster.

16

A: Golf a number bigger than TREE(3)

Ruby, 329 bytes, Hψ0(Ω9)(9) where H is the Hardy hierarchy and ψ is an ordinal collapsing function described below. Try it online! def f(b,n=0,x=0)c,d=b;n<1?(b.class!=Array):x>0?(b==1?n:f(f(b,n),n*n,1)):f(b)?(b>1?b-1:n):b.size>2?h(n,c,d):[c,!f(d)?f(d,n):d>1?d-1:d>0?c:n]end;def h(n,a,b)(x=b!=0?...

If you are looking at my answer and you are wondering how large my ordinal is, we can chat about that on another day...

ASCII-only

Mathis is weird

scottaaronson.com/blog/?p=2725

Simply Beautiful Art

@wizzwizz4 =) Hopefully you also now comprehend the magnitude of TREE(3).

wizzwizz4

13:44

@ASCII-only What do you mean?

ASCII-only

like is it that obvious that BB(n) >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> TREE^{TREE(n)}(n)

Simply Beautiful Art

@ASCII-only yes?

Left side is not computable, right side is computable.

not computable >> computable

wizzwizz4

I just stopped treating it as a concept and startined treating it as sums.

@SimplyBeautifulArt No. I'm not even close.

Simply Beautiful Art

=P

There's actually a much quicker way to reach TREE(n)

So the moral of the story here is that to make a really large finite number, use a really large and computable ordinal.

Imagine if we repeated this story in the following manner:
To make a really large and computable ordinal, use an even larger ordinal, one so large as to be uncomputable.

That is, "collapse" these 'super-ordinals' down to manage-able ordinals, and collapse those into finite numbers.

This is where the term "ordinal collapsing function" comes from

You can imagine to make these large uncomputable ordinals, we can use even larger ordinals...

I basically took this process 9 times in my program and outputted the final result....

wizzwizz4

There is such thing as an uncomputable ordinal?

Simply Beautiful Art

13:53

Church–Kleene ordinal

In mathematics, the Church–Kleene ordinal, ω 1 C K {\displaystyle \omega _{1}^{\mathrm {CK} }} , named after Alonzo Church and S. C. Kleene, is a large countable ordinal. It is the set of all recursive ordinals and the smallest non-recursive ordinal. It is also the first ordinal which is not hyperarithmetical, and the first admissible ordinal after ω. == References == Church, Alonzo; Kleene, S. C. (1937), "Formal definitions...

uncomputable = non-recursive.

Usually we use uncountable ordinals though

Since more people know/accept uncountable ordinals than uncomputable ordinals.

@wizzwizz4 Do you know what a bijection is?

wizzwizz4

0

A: Sandbox for Proposed Challenges

Two-Symbol n-state Universal Turing Machine A program is defined as a set of transition rules from one state to another based on the current state and symbol, optionally moving the tape head left or right. The goal is to produce a program that satisfies all of the following criteria: It is a ...

Simply Beautiful Art

Unfortunately I haven't studied much about Turing machines yet

wizzwizz4

@SimplyBeautifulArt A mapping via a reversible function?

trichoplax

> a Turing machine to test whether all perfect squares are less than 5, produced using Laconic, needed to run for more than an hour before it found the first counterexample (namely, 3^2=9) and halted

Wow. That's some seriously golfed code. Optimised for length only

Simply Beautiful Art

@wizzwizz4 Imagine the smallest set that does not have a bijection to ω, the set of all natural numbers.

The resulting set is equal to ω_1, or in terms of ordinal collapsing functions, Ω_1. In my program, this is [1].

wizzwizz4

13:59

A Turing Machine is essentially an esoteric programming language.

Simply Beautiful Art

@wizzwizz4 hm, okay.

ASCII-only

@wizzwizz4 math is essentially an esoteric programming language :P

Simply Beautiful Art

@trichoplax x'D

xD

wizzwizz4

@SimplyBeautifulArt That'll get big.

ASCII-only

you can do anything with abs, floor, ceil magic and things like that:

The 'Everything' Formula - Numberphile

►

feersum

14:01

@trichoplax It really isn't. It's compiled from a high level language which really blows up the size with extra layers of abstraction.

Simply Beautiful Art

@wizzwizz4 Any particular functions you'd like to know the ordinal approximation of?

wizzwizz4

Each instruction is followed by a goto.

trichoplax

@feersum I understand that it's not hand-golfed, and not optimally golfed. I'm just amused by how far from optimal it is in terms of run speed

wizzwizz4

The goto determineds the next state to use.

Each state is a switch statement on the data under the tape head.

There's an infinite tape, and there's a tape pointer.

flawr

did you guys see this wooden TM model?

feersum

14:05

It's weird how this one totally arbitrary model of computation is so much studied, due to only a historical accident of being the first one posed in conjunction with a Busy Beavers problem.

wizzwizz4

Each instruction is a combination of three stages - write to the tape a specific symbol (under the tape head), then move one space left or right (or don't move) and change state.

Nathan Merrill

@feersum I mean, isn't this true for any branch of mathematics?

wizzwizz4

The two-symbol Turing machine is special because it's the Turing Machine with the fewest symbols that has been proven to be Turing complete.

feersum

@NathanMerrill I disagree.

trichoplax

Unlosable hydra game

unloseable?

Simply Beautiful Art

14:26

@trichoplax yes

Fun fact: Try writing the hydra in terms of ordinals, and you can derive how long it takes to kill a hydra.

trichoplax

Would that give the upper bound on how many moves it will take if you try not to win?

Simply Beautiful Art

No. If you do it correctly, it gives an exact value for how many moves it will take.

trichoplax

So the worst you can do is also the best you can do?

Simply Beautiful Art

@trichoplax no, worst = more moves, best = less moves.

Using ordinals, you can probably derive expressions for both.

Kill the Mathematical Hydra | Infinite Series

►

^ See there

trichoplax

I didn't realise it would work for best too. Interesting

Simply Beautiful Art

14:31

Well you just have to define proper rules.

Loool

PBS fails to write ordinal operations in proper order.

feersum

"Infiite Series"? Seems that they have already made a mistake in the title.

Simply Beautiful Art

@feersum its just the name of the channel.

feersum

Then clearly hydra games should not be permitted in this channel.

Simply Beautiful Art

@feersum :P. "Infinite series" is merely the math section of PBS.

How Infinity Explains the Finite | Infinite Series

►

This is related to the Goodstein sequence, which is related to Output the simplified Goodstein sequence.

An example of how one can use ordinals to derive expressions for the lengths of certain sequences is shown in Counterintuitive Goodstein's Theorem.

Simply Beautiful Art

15:00

@wizzwizz4 @fejfo If you are interested in how my program works, I basically apply recursion over addition and functions.

f(1,n,1) = n
f(a+1,n,1) = f(a,n^2,1)
f(a,n,1) = f(a[n,a],n^2,1)

ω[n,b] = n
(a+1)[n,b] = a
(a+b)[n,b] = a+(b[n,b])

ψ'_0(0)[n,b] = ω+ω
ψ'_a(0)[n,b] = Ω_a+Ω_a
ψ'_a(b+1)[n,b] = ψ'_a(b)+ψ'_a(b)
ψ'_a(b)[n,b] = ψ'_a(b[n,b]) + ψ'_a(b[n,b])

(Ω_a)[0,b] = ω
(Ω_a)[n,b] = ψ'_(a-1)(b)[n-1,b]

Wheat Wizard

@SimplyBeautifulArt Did you ever solve that puzzle I gave you?

Simply Beautiful Art

Where my final output is f(ψ'_0(Ω_9),n,1)

@WheatWizard :o no. Did you ever solve mine?

Wheat Wizard

Unfortunately I haven't had time, been spending time doing math I'm "supposed" to do so that I can "pass" my classes.

Simply Beautiful Art

lol

Well, you can probably figure out what I've been doing

Wheat Wizard

Once monday passes I will have time to work on other stuff again, so I'll take another less tired look at the problem.

Simply Beautiful Art

15:04

Well, hopefully you'll figure out a hint or two by reading the above conversation

Wheat Wizard

That's what reminded me.

Simply Beautiful Art

:P

fejfo

16:40

@SimplyBeautifulArt returning to 15:01, I know Peano Arithmetic is a minimalistic version of math with no infinite sets, I don't know much more.

ε_1 = {1, ε_0, ε_0^ε_0, ...} but it is also = {ε_0+1, ω^(ε_0+1), ω^ω^(ε_0+1), ...} right (using your n-th fixed point definition from yesterday)

f(1,n,1) = n
f(a+1,n,1) = f(a,n^2,1)
f(a,n,1) = f(a[n,a],n^2,1)

ω[n,b] = n
(a+1)[n,b] = a
(a+b)[n,b] = a+(b[n,b])

ψ'_0(0)[n,b] = ω+ω
ψ'_a(0)[n,b] = Ω_a+Ω_a
ψ'_a(b+1)[n,b] = ψ'_a(b)+ψ'_a(b)
ψ'_a(b)[n,b] = ψ'_a(b[n,b]) + ψ'_a(b[n,b])

Simply Beautiful Art

Oh yeah. Peano Arithmetic can't prove that H(n, a) is finite for all natural n and a ≥ ε_0.
Your definition of ε_1 is also valid.

a[n,a] works just like a[n]. The only difference occurs once you reach the ordinal collapsing functions

fejfo

17:09

Ω_a is that the a-th inaccessible ordinal (the a-th ordinal you can't reach by replacement of a previous set) ? I will try to work your function out a bit just to see where it takes me

Simply Beautiful Art

@fejfo Yeah, you can think of Ω_a like that.

The idea is that ψ'_0(Ω_2)[3,b] = ψ'_0(ψ'_1(ψ'_1(ψ'_1(ω))))

That is, it causes a nesting.

If you had ψ'_0(Ω_5+Ω_2)[3,b], then it would reduce to
ψ'_0(Ω_5+ψ'_1(Ω_5+ψ'_1(Ω_5+ψ'_1(Ω_5+ω))))

^ It nests the operation ψ'_1(Ω_5+x)

Imagine it this way. ψ'_x produces lots and lots of Ω_x.

Ω_x reduces down to ψ'_(x-1)(y)

where y is the "string of ordinals" that Ω_x was in

In the above example, Ω_2 was inside the string Ω_5+x, so it reduced to ψ'_1(Ω_5+x)

fejfo

let me try to work out ψ'_0(Ω_2)[3,b] by myself

ψ'_0(Ω_2)[3,b] = ψ'_0(Ω_2[3,b]) + ψ'_0(Ω_2[3,b])
Ω_2[3,b]=ψ'_1(b)[2,b] =

Simply Beautiful Art

@fejfo Nuh uh.

ψ'_a(b)[n,b] = ψ'_a(b[n,b]) + ψ'_a(b[n,b])

So after the first inequality, b = Ω_2

Oh shoot, that rule is messed up

It should be
ψ'_a(x)[n,b] = ψ'_a(x[n,x]) + ψ'_a(x[n,x])

My bad

fejfo

@SimplyBeautifulArt yes you seem to have b twice theire

So let's try again: wait are you sure the x replaces the b in x[n,x] not x[n,b] ?

Simply Beautiful Art

17:25

Yes, I am sure

Sure gets lengthy pretty fast.

@fejfo For simplicity, you may wish to use the alternative:
ψ'_0(0)[n,b] = ω
ψ'_a(0)[n,b] = Ω_a
ψ'_a(b+1)[n,b] = ψ'_a(b)
ψ'_a(x)[n,b] = ψ'_a(x[n,x])
Which obviously doesn't grow much, but may be better for insight.

fejfo

so leave out the "*2" hmmm maybe I could just cheat and put a *2^n at the end instead it should mean the same thing I think (although not well defined in your code)

Simply Beautiful Art

@fejfo I suppose you could.

fejfo

17:41

ψ'_0(Ω_2)[3,b]=ψ'_0(Ω_2[3,Ω_2])*2>ψ'_0( ψ'_1(ψ'_1(ψ'_1(ω))))
Ω_2[3,Ω_2]=ψ'_1(Ω_2)[2,Ω_2] = ψ'_1(Ω_2[2,Ω_2])*2=ψ'_1(ψ'_1(ψ'_1(ω)*2)*2)*2 > ψ'_1(ψ'_1(ψ'_1(ω)))
Ω_2[2,Ω_2]=ψ'_1(Ω_2)[1,Ω_2]=ψ'_1(Ω_2[1,Ω_2])*2=ψ'_1(ψ'_1(ω)*2)*2
Ω_2[1,Ω_2]=ψ'_1(Ω_2[0,Ω_2])*2=ψ'_1(ω)*2
Ω_2[0,Ω_2]=ω

ψ'_0(Ω_2)[3,b] seems to nest ψ'_1 3 times does this generalize?

Simply Beautiful Art

@fejfo yes

Try doing ψ'_0(Ω_2+Ω_2)[3,b]

fejfo

@SimplyBeautifulArt can I do it on paper? It writes much quicker

Simply Beautiful Art

@fejfo yeah ofc

Just try to limit yourself to 2 pages front+back

I consumed a whole notebook just on ordinal collapsing functions.

fejfo

how long did you spend on this stuff?

Simply Beautiful Art

@fejfo A few months.

fejfo

17:58

@SimplyBeautifulArt wow, look at that it generates a bunch of Ω_2+ in the recursion, I'm guessing those can restart the whole Ω_2 process when you've finally worked out ψ'_1(Ω_2+ω)

Simply Beautiful Art

@fejfo Yeup. Very powerful recursion technique.

Note that each ψ'_1 eventually reduces down to Ω_1's

fejfo

@thinking of ψ'_1(ω) I've no idea how ψ' handles ω

@SimplyBeautifulArt oeps forgot to write your name there

Simply Beautiful Art

@fejfo ψ'_a(x)[n,b] = ψ'_a(x[n,x]) + ψ'_a(x[n,x]), where ω[n,b] = n

Transcript for