ConwayLife.com

Posted: **September 8th, 2019, 4:31 pm**

A question about the game of hive:
Suppose that, in this scenario:
Black's objective is to win by surrounding the white bee with pieces of any color or to force white to forfeit by making it so that white has no moves on their turn.
White's objective is to make the game last forever.
Who wins, and if black does, after how long? (Assuming both play optimally)

: The cyan thing is the pill bug and the grey the mosquito; 3EC48C4B-65F6-45A6-A38F-4F3313C06D69.jpeg (342.89 KiB) Viewed 9314 times

Obviously, moving the Mosquito onto the Pillbug is a losing move since a beetle could then get on top of that.
Note that, according to boardgamegeek, Mosquitoes can use the pillbug's ability (iff they are adjacent to one of course)

Posted: **September 10th, 2019, 3:46 pm**

What is the growth rate of this, in the fgh?

Posted: **September 16th, 2019, 8:33 pm**

Moosey wrote:What is the growth rate of this, in the fgh?

Under a stronger version where a copies are made instead of two, I get this analysis:

Code: Select all

a{1,1,1}e = a(^e)a
a{1,c,1}1 = a{a{a,c-1,a}a,c-1,a}a
a{b,c,1}1 = a{b-1,c,a{b-1,c,1}a}a
a{b,c,d}1 = a{b,c,d-1}a{b,c,d-1}a
a{b,c,d}0 = a

a{1,1,1}a = w (1)
a{1,1,2}a = w+1 (4)
a{1,1,a}a = w2
a{2,1,1}a = w2+1 ? (3)
a{2,1,a}a = w3
a{3,1,1}a = w3+1 (3)
a{a,1,1}a = w^2
a{1,2,1}a = w^2+1 ? (2)
a{1,a,1}a = w^3

Parenthesized numbers point to the relevant (clarified) rules.

Posted: **September 21st, 2019, 9:54 am**

Is it possible to define an infinite sequence of ordinals such that for all o less than w_1, you have only gone past a finite amount of ordinals in the sequence?
Formally:
Is ∃(A)∀(o|o<|(w_1))∀(B|[∀n|n<o,n∈A⇔n∈B]∧[∄(C|C⊊B∧[∀n|n<o,n∈A⇔n∈C])])(|B|<w∧|A|>=w) a true statement?

EDIT:
Thanks macbi

Posted: **September 21st, 2019, 11:59 am**

Moosey wrote:Is it possible to define an infinite sequence of ordinals such that for all o less than w_1, you have only gone past a finite amount of ordinals in the sequence?
Formally:
Is ∃(A)∀(o|o<|(w_1))∀(B|[∀n|n<o,n∈A⇒n∈B]∧[∄(C|C⊂B∧[∀n|n<o,n∈A⇒n∈B])])(|B|<w∧|A|>=w) a true statement?

I think in your formalisation you want "⇔" instead of "⇒ "both times, and you want "C|C⊂B∧[∀n|n<o,n∈A⇒n∈B" to end with "C" rather than "B". Also note that "⊂" is ambiguous since some annoying people use it to mean "is a subset of" rather than "is a strict subset of". I think you do want a strict subset, so it's better to use "⊊".

In any case, look at the well order induced on A. This had better have order-type w or else there will be some ordinal preceded by an infinite number of elements of A. So A is a countable subset of w_1, and for every o in w_1 we have some a in A with o<a (or else o would have an infinite number of as below it). Thus we can write w_1 as the union over a in A of the set of ordinals less than a. This is a contradiction because a countable union of countable sets is countable.

See also: Cofinality.

Posted: **September 23rd, 2019, 8:33 am**

What are next terms in this sequence?
123454321
121232123432123454321234321232121
How fast does it grow?

EDIT:
it's related to n-> 1234...n....4321 but not the same-- that sequence is
5
123454321
11211232112343211234543211234321123211211

Posted: **September 24th, 2019, 6:22 pm**

What is the longest-lasting (I.e. one with the largest corresponding lifespan ordinal) position in infinite chess if fairy pieces are allowed?
(Note: an excellent summary of the w^4 position is here.)
Would it be possible, to, say, somehow fit multiple probably-not-rook-towers-anymore together and get w^4 for the towers alone, and then add the bishop cannon at the bottom of the for w^5?
Obviously, we can use zeros instead of pawn couples, for 1x1 wall units instead of 1x2 wall units

Would it be possible to build "wazir channels" where wazirs climb around analogously to rook towers?
e.g.
0 0 0 0 0
0 w 0 w 0
0 d 0 0 0
0 . 0 NN 0
0 . 0 0 0

->

0 0 0 0 0
0 w 0 . 0
0 d 0 w 0
0 . 0 NN 0
0 . 0 0 0

->

0 0 0 0 0
0 w 0 . 0
0 d 0 . 0
0 . 0 w 0
0 . 0 0 0

->

0 0 0 0 0
0 w 0 . 0
0 . 0 d 0
0 . 0 w 0
0 . 0 0 0

This freeing the second wazir. Presumably the dabbaba is pinned (at least in terms of optimal play) by the knightrider which would also immediately cause a loss for team red if it moved to capture the dababba. Or just in general, the dababba is pinned so it cannot capture the 0.

EDIT:
Is it possible to make a version of the rook towers or something similar, but linear instead of taking up 1/8th of the plane?

Posted: **September 25th, 2019, 2:54 pm**

Moosey wrote:What are next terms in this sequence?
123454321
121232123432123454321234321232121
How fast does it grow?

I'm not as good at maths as you all, but I think that the sequence will stabilize and will tend to be normal (all the digits are equally frequent). Every digit n will be replaced with 2(n-1) digits and the average is

(2(1-1)+2(2-1)+2(3-1)+2(4-1)+2(5-1))/5 = 2(1+2+3+4)/5 = 2*10/5 = 20/5 = 4.

That means that the number of digits in f(x) is on average 4 times bigger than f(x-1).

The approximate growth rate of your function is O(10^(4^n)).

Posted: **September 25th, 2019, 4:14 pm**

gameoflifemaniac wrote:
Moosey wrote:What are next terms in this sequence?
123454321
121232123432123454321234321232121
How fast does it grow?
I'm not as good at maths as you all, but I think that the sequence will stabilize and will tend to be normal (all the digits are equally frequent). Every digit n will be replaced with 2(n-1) digits and the average is

(2(1-1)+2(2-1)+2(3-1)+2(4-1)+2(5-1))/5 = 2(1+2+3+4)/5 = 2*10/5 = 20/5 = 4.

That means that the number of digits in f(x) is on average 4 times bigger than f(x-1).

The approximate growth rate of your function is O(10^(4^n)).

that would almost be the sequence

Code: Select all

5
123454321
11211232112343211234543211234321123211211
111211112112321121111211232112343211232112111121123211234321123454321123432112321121111211232112343211232112111121123211211112111

which one can find here.
Speaking of those,
this sequence is much more closely related to the one we're talking about. If you look at the wolfram alpha graph and switch it to log scale it appears it is not exponential in growth rate.
also, your math doesn't exactly make sense-- you have to weight the average, since you have many more 1s and 2s than 4s or 5s

Posted: **October 10th, 2019, 11:15 am**

Are there any values of x where |x|=-1 or |x|=i, in any algebra that has been invented before?

Posted: **October 14th, 2019, 7:00 am**

What is the magnitude of w1ch3? (w1 of 3D chess)?
Calcyman proved 3D chess is TC, so theoretically, could it be as large as w_1ck?

Posted: **October 14th, 2019, 2:44 pm**

The paper Transfinite Game Values in Infinite Chess (which also provides an infinite 2D chess position with a value of ω^3) proves that with infinite configurations, the ordinal of 3d chess (it also works on 3D chess with finite but sufficiently large thickness) is ω_1 (first uncountable ordinal). With finite positions, I'm not so sure, because all constructions for Turing-completeness involve multiple kings (however, it might be possible to substitute them with tons of queens or something).

Posted: **October 24th, 2019, 5:21 pm**

Can someone explain bashicu matrix systems?

I think I understand what this file is trying to say, but not much else:
https://googology.wikia.org/wiki/File:BMS_expansion.png

Posted: **October 24th, 2019, 9:48 pm**

Moosey wrote: October 24th, 2019, 5:21 pm Can someone explain bashicu matrix systems?

I think I understand what this file is trying to say, but not much else:
https://googology.wikia.org/wiki/File:BMS_expansion.png

I'll try my best to paraphrase what goes on for BM2.3:

If your last column is all zeroes, your matrix is a successor, and you simply drop it.
Otherwise, we have to expand.

First, we have to define parents: The parent of a cell is the nearest cell to its left which is less than it and also a parent of some degree in the row above. (The last condition is vacuously true for the top row.)

Now we're ready to roll. Call the row containing the lowermost nonzero element in the last column the bad row, and the column containing the parent of that element the bad root. Everything before the bad root is the good part, while the section from the bad root to the second-last column is the bad part.

The good part of our expanded matrix is the same as the one in our original matrix, and the new bad part is found by doing the following n times:
- Add a copy of the bad part (with last row removed).
- Increase each cell in the bad part above the bad row by the difference between the last column and the bad root (in that row) if the bad root contains a parent (of some degree) of that cell.

An example: Consider (0,0,0)(1,1,1)(2,2,1)(3,3,0)[3]. I'll be using [x,y] to refer to the cell in column x and row y, with the upper left being [1,1].
The bad row is the second row, so the bad root is the column containing the parent of [4,2].
We first check [3,2], and see that [3,1] is a direct parent of [4,1], making [3,2] the parent of [4,2] and (2,2,1) the bad root.
Our good part is (0,0,0)(1,1,1) and our bad part is (2,2,1).
First pass: We add back our bad part. Our new matrix is (0,0,0)(1,1,1)(2,2,1).
Then we increase the bad part. The difference between (2,2,1) and (3,3,0) is (1,0,0) since we don't increase anything at or below the bad row, and adding this to the bad root gives (3,2,1)*.
Second pass: Our new matrix is (0,0,0)(1,1,1)(2,2,1)(3,2,1).
Increasing works exactly the same as before, making the bad part (4,2,1).
Third pass: Our new matrix is (0,0,0)(1,1,1)(2,2,1)(3,2,1)(4,2,1), and we're done!

* I don't need to check the parenthood condition because my bad part has length one and we can say that each column is a 0'th-degree parent of itself. I don't recall seeing a description of BMS that addresses this, however.

Posted: **October 25th, 2019, 11:59 am**

There's an online BMS calculator at http://gyafun.jp/ln/basmat.cgi (note that BM4 and BM2.3 are generally considered to be identical)

Posted: **October 26th, 2019, 2:47 pm**

If I define simple psi thusly:

Code: Select all

C_0(a) = {0,1,W}
C_n+1(a) = C_n(a) U {b+c,ψ(d),b∈C_n(a),c∈C_n(a),d<a,d∈C_n(a)}
C(a) = U(n<w)(C_n(a))
ψ(a) = the smallest countable ordinal not in C(a)

what is ψ(W) ? (W = w_1)
EDIT: it's e_0, and the limit of simple psi is e_w

In LaTeX that's this:
\begin{eqnarray*} C_0(\alpha) &=& \{0, 1, \Omega\}\\ C_{n+1}(\alpha) &=& \{\gamma + \delta, \psi(\eta) | \gamma, \delta, \eta \in C_n (\alpha); \eta < \alpha\} \\ C(\alpha) &=& \bigcup_{n < \omega} C_n (\alpha) \\ \psi(\alpha) &=& \min\{\beta \in \Omega|\beta \notin C(\alpha)\} \\ \end{eqnarray*}

With all fairness, testitemqlstudop, how is using LaTeX going to make complex definitions easier to understand? It only adds a step-- running to some LaTeX viewer, like the one here.

Posted: **November 4th, 2019, 11:24 am**

Is there any lower bound on how quickly the Busy Beaver function grows?

Posted: **November 4th, 2019, 6:29 pm**

gameoflifemaniac wrote: November 4th, 2019, 11:24 am Is there any lower bound on how quickly the Busy Beaver function grows?

Any computable function suffices.

Posted: **November 5th, 2019, 11:35 am**

: 522b0d8b1ba37b84.jpg (32.05 KiB) Viewed 8283 times

Help

Posted: **November 5th, 2019, 12:24 pm**

GUYTU6J wrote: November 5th, 2019, 11:35 am 522b0d8b1ba37b84.jpg
Help

A useful identity here that may help: f(x)^g(x) = e^(g(x)ln(f(x)) — because f(x)^g(x) = e^(ln(f(x)^g(x))), which can be expanded using the properties of logarithms.

Posted: **November 5th, 2019, 1:26 pm**

BlinkerSpawn wrote: November 4th, 2019, 6:29 pm
gameoflifemaniac wrote: November 4th, 2019, 11:24 am Is there any lower bound on how quickly the Busy Beaver function grows?
Any computable function suffices.

If all uncomputable functions eventually surpass all fast-growing hierarchy functions, how do you compare them? Is there a separate notation to describe their growth rate?

Posted: **November 5th, 2019, 5:32 pm**

gameoflifemaniac wrote: November 5th, 2019, 1:26 pm
BlinkerSpawn wrote: November 4th, 2019, 6:29 pm
gameoflifemaniac wrote: November 4th, 2019, 11:24 am Is there any lower bound on how quickly the Busy Beaver function grows?
Any computable function suffices.
If all uncomputable functions eventually surpass all fast-growing hierarchy functions, how do you compare them? Is there a separate notation to describe their growth rate?

Computables slower than uncomputables DOES NOT mean the fgh is slower than uncomputable.
You can index the fgh with w_1ck, and therefore the fgh doesn't necessarily need to be computable*

*Though as far as I know, nobody has a fundamental sequence for w_1ck, so you can't really evaluate f_w_1ck(n) without some innovation

Posted: **November 11th, 2019, 6:15 pm**

How much more powerful is ah_n(a(@@a)a) compared to f_a(n)?

Posted: **November 12th, 2019, 12:12 am**

Moosey wrote: November 11th, 2019, 6:15 pm How much more powerful is ah_n(a(@@a)a) compared to f_a(n)?

I'll need a clarification of the rules before I can answer, which I've already asked you for.
At least, I hope that was you from the Googology Discord that I messaged about this.

Posted: **November 12th, 2019, 7:17 am**

BlinkerSpawn wrote: November 12th, 2019, 12:12 am
Moosey wrote: November 11th, 2019, 6:15 pm How much more powerful is ah_n(a(@@a)a) compared to f_a(n)?
I'll need a clarification of the rules before I can answer, which I've already asked you for.
At least, I hope that was you from the Googology Discord that I messaged about this.

No it wasn't
I'm not on the googology discord. The problem is that fluffykitty put invites to the discord everywhere and somebody else decided to join and attempt to impersonate me. Just ignore anything they say.

What kind of clarification do you need?

Here are the complete-at-the-moment ah rules:

Code: Select all

Part one:

define $_n as any entries (including no entries) in an array.
It’s my symbol for we-don’t-care entries.
In any one use of any one rule, if n is the same, $_n is the same

a#b = concatenation of a and b

n@m =
n, m = 1
{n}#(n@(m-1)), m > 1, m not a lim ord
n@(m[n]) if m is a lim ord

g(a,n,B) =
ah_g(a-1,n,B) {B}, a > 1;
n, a = 0

ah definition:
Rule 1.
ah^a_n {$_0} = g(a,n,$_0)
Rule 2.
ah_n ({$_1}#{z}) = ah_n {$_1}, z = 0
Rule 3.
ah_n{} = n+1
Rule 4.
ah_n{a+1,$_2} = ah^n_n{a,$_2}
Rule 5.
ah_n{a,$_3} = ah_n{a[n],$_3}, a a lim ord
Rule 6.
ah_n ((0@b)#{a+1,$_4}) = ah_(n+1) (((a+1)@b)#{a,$_4}), b > 0
Rule 7.
ah_n ((0@b)#{a,$_5}) = ah_n ((a@b)#{a[n],$_5}), a a lim ord & b > 0

The rest of the array rules:
ah_n{$_0//(b+1),$_1} = ah_n((($_0)(@^_n)ah_n{$_0//b})#{//b,$_1})
ah_n{$_0//0} = ah_n{$_0}
ah_n{$_0//b,$_1} = ah_n{$_0//(b[n]),$_1} for lim ord b
Else: apply ah's 7 rules, starting after legion bar. (e.g. ah_{$_0//,0,0,w+1} = ah_{$_0//,w+1,w+1,w})

($_1)(@^_n)a =
($_1)@(ah_n(($_1)(@^_n)(a-1))), a > 1,
ah_n{$_1}, a=1

ah_n{$_0@@0} = ah_n{$_0}
ah_n{$_0@@a,$_1} = ah_n{$_0@@a[n],$_1},a a lim ord
ah_n{$_0@@(a+1),$_1} = ah_n({$_0//}#{$_0@@(a),$_1}
Apply basic ah rules otherwise to everything after the @@

ah_n{$_0(@@b,$_2)0} = ah_n{$_0}
ah_n{$_0((@@b,$_2)a,$_1} = ah_n{$_0(@@b)a[n],$_1},a a lim ord
ah_n{$_0(@@0)(a+1),$_1} = ah_n({$_0//}#{$_0(@@0)(a),$_1}
ah_n{$_0(@@b+1,$_2)(a+1),$_1} = ah_n({$_0(@@b,$_2)}#{$_0@@(a),$_1}
ah_n{$_0(@@b,$_2)$_3} = ah_n{$_0(@@b[n],$_2)$_3}, if b is a lim ord
Apply basic ah rules otherwise to everything after the (@@$) or everything inside the (@@$) depending on what is necessary

These array rules can be applied without the ah_n of the array, but any n refers to the n in the ah subscript.

ConwayLife.com

Thread for Non-CA Academic Questions

Re: Thread for Non-CA Academic Questions

Re: Thread for Non-CA Academic Questions

Re: Thread for Non-CA Academic Questions

Re: Thread for Non-CA Academic Questions

Re: Thread for Non-CA Academic Questions

Re: Thread for Non-CA Academic Questions

Re: Thread for Non-CA Academic Questions

Re: Thread for Non-CA Academic Questions

Re: Thread for Non-CA Academic Questions

Re: Thread for Non-CA Academic Questions

Re: Thread for Non-CA Academic Questions

Re: Thread for Non-CA Academic Questions

Re: Thread for Non-CA Academic Questions

Re: Thread for Non-CA Academic Questions

Re: Thread for Non-CA Academic Questions

Re: Thread for Non-CA Academic Questions

Re: Thread for Non-CA Academic Questions

Re: Thread for Non-CA Academic Questions

Re: Thread for Non-CA Academic Questions

Re: Thread for Non-CA Academic Questions

Re: Thread for Non-CA Academic Questions

Re: Thread for Non-CA Academic Questions

Re: Thread for Non-CA Academic Questions

Re: Thread for Non-CA Academic Questions

Re: Thread for Non-CA Academic Questions