User:Polygon/Better lower bound for BB(4,3): Difference between revisions

From BusyBeaverWiki
Jump to navigation Jump to search
← Older edit
VisualWikitext
Polygon (talk | contribs)
2,286 edits
Fixed weird headings
Polygon (talk | contribs)
2,286 edits
Added an even more precise upper bound
 
(3 intermediate revisions by the same user not shown)
Line 1: Line 1:
Machine: {{TM|0RB1RZ0RB_1RC1LB2LB_1LB2RD1LC_1RA2RC0LD|halt}}
=Better lower bound for BB(4,3)=
=Better lower bound for BB(4,3)=
==Definitions==
==Definitions==
Line 20: Line 21:


<math>=> f^{n}(0) > 2 \uparrow\uparrow 2n</math>
<math>=> f^{n}(0) > 2 \uparrow\uparrow 2n</math>
'''Upper bound'''
<math>f_{u}(n)=2^{2^{2^{n}}}; f_{u}(0)=2^{2^{2}}; f_{u}^{0}(0) = 1</math>
<math>f_{u}(n) > f(n)</math> as <math>2^{n} > n+1</math>
<math>f_{u}^{k}(0) = (2 \uparrow)^{3}f_{u}^{k-1}(0)</math>
<math>f_{u}^{2}(0) = f_{u}(2^{2^{2}}) = 2^{2^{2^{2^{2^{2}}}}} => (2 \uparrow)^{6}1</math>
<math>f_{u}^{k}(0) = (2 \uparrow)^{3k}1 = 2 \uparrow\uparrow 3k; f_{u}(n) > f(n) => 2 \uparrow\uparrow 3k > f(n)</math>
<math>f^{n}(0) < 2 \uparrow\uparrow 3n</math>
==Lower bound on g^k(n)==
==Lower bound on g^k(n)==
<math>g(n) = \frac {5 \times 2^{2^{f^{n}(0)+1}+2}-8}{9} > \frac {5 \times 2^{2^{2 \uparrow\uparrow 2n}+2}-8}{9} > 2^{2^{2 \uparrow\uparrow 2n}} = 2 \uparrow\uparrow (2n+2)</math>
<math>g(n) = \frac {5 \times 2^{2^{f^{n}(0)+1}+2}-8}{9} > \frac {5 \times 2^{2^{2 \uparrow\uparrow 2n}+2}-8}{9} > 2^{2^{2 \uparrow\uparrow 2n}} = 2 \uparrow\uparrow (2n+2)</math>
Line 29: Line 44:
<math>g^{k}(n) > (2 \uparrow\uparrow)^{k}(2n+2) > (2 \uparrow\uparrow)^{k}2n</math>
<math>g^{k}(n) > (2 \uparrow\uparrow)^{k}(2n+2) > (2 \uparrow\uparrow)^{k}2n</math>


'''Upper bound'''
<math>g(n) = \frac {5 \times 2^{2^{f^{n}(0)+1}+2}-8}{9} < \frac {5 \times 2^{2^{(2 \uparrow\uparrow 3n)+1}+2}-8}{9} < 5 \times 2^{2^{(2 \uparrow\uparrow 3n)+1}+2} < 2 \uparrow\uparrow (3n+3)</math>
<math>g^{2}(n) < 2 \uparrow\uparrow (3 \times (2\uparrow\uparrow (3n+3))+3) < 2 \uparrow\uparrow 2 \uparrow\uparrow (3n+4)</math>
<math>g^{k}(n) < 2 \uparrow\uparrow (3 \times (g^{k-1}(n))+3) < 2 \uparrow\uparrow 2 \uparrow g^{k-1}(n)</math>
<math>g^{k}(n) < (2 \uparrow\uparrow)^{k}(3n+k+2)</math>
==Lower bound on g^n1(n0)==
==Lower bound on g^n1(n0)==
<math>g^{n1}(n0) = g^{2^{2^{32}+1}-4}(\frac {5 \times 2^{2^{2^{32}+1}+1}-4}{9}) > g^{2^{2^{32}+1}-4}(2^{2^{2^{32}}}) > (2 \uparrow\uparrow)^{2^{2^{32}+1}-4}2^{2^{2^{32}}}</math> ; Note that <math>2 \uparrow\uparrow 6 < 2^{2^{2^{32}}} < 2 \uparrow\uparrow 7</math>
<math>g^{n1}(n0) = g^{2^{2^{32}+1}-4}(\frac {5 \times 2^{2^{2^{32}+1}+1}-4}{9}) > g^{2^{2^{32}+1}-4}(2^{2^{2^{32}}}) > (2 \uparrow\uparrow)^{2^{2^{32}+1}-4}2^{2^{2^{32}}}</math> ; Note that <math>2 \uparrow\uparrow 6 < 2^{2^{2^{32}}} < 2 \uparrow\uparrow 7</math>
Line 35: Line 59:


<math>g^{n1}(n0) > (2 \uparrow\uparrow)^{2^{2^{32}+1}-2}2</math>
<math>g^{n1}(n0) > (2 \uparrow\uparrow)^{2^{2^{32}+1}-2}2</math>
'''Upper bound'''
<math>g^{n1}(n0) = g^{2^{2^{32}+1}-4}(\frac {5 \times 2^{2^{2^{32}+1}+1}-4}{9}) < (2 \uparrow\uparrow)^{2^{2^{32}+1}-4}(3 \times (\frac {5 \times 2^{2^{2^{32}+1}+1}-4}{9}) + 2^{2^{32}+1}-4 + 2) < (2 \uparrow\uparrow)^{2^{2^{32}+1}-4}2 \uparrow\uparrow 7 => (2 \uparrow\uparrow)^{2^{2^{32}+1}-3}7</math>
<math>g^{n1}(n0) < (2 \uparrow\uparrow)^{2^{2^{32}+1}-3}7</math>
or, for a more precise upper bound:
<math>g^{n1}(n0) = g^{2^{2^{32}+1}-4}(\frac {5 \times 2^{2^{2^{32}+1}+1}-4}{9}) < (2 \uparrow\uparrow)^{2^{2^{32}+1}-4}(3 \times (\frac {5 \times 2^{2^{2^{32}+1}+1}-4}{9}) + 2^{2^{32}+1}-4 + 2) < (2 \uparrow\uparrow)^{2^{2^{32}+1}-4}(2^{2^{2^{33}}})</math>
<math>g^{n1}(n0) < (2 \uparrow\uparrow)^{2^{2^{32}+1}-4}(2^{2^{2^{33}}})</math>
or, for an even more precise upper bound:
<math>(2 \uparrow\uparrow)^{2^{2^{32}+1}-4}(3 \times (\frac {5 \times 2^{2^{2^{32}+1}+1}-4}{9}) + 2^{2^{32}+1}-4 + 2) < (2 \uparrow\uparrow)^{2^{2^{32}+1}-4}(2^{2^{2^{32}+2}})</math>
<math>g^{n1}(n0) < (2 \uparrow\uparrow)^{2^{2^{32}+1}-4}(2^{2^{2^{32}+2}})</math>
==Lower bound on f^g^n1(n0)(0)==
==Lower bound on f^g^n1(n0)(0)==
<math>g^{n1}(n0) > (2 \uparrow\uparrow)^{2^{2^{32}+1}-2}2</math> and <math>f^{n}(0) > 2 \uparrow\uparrow 2n</math>
<math>g^{n1}(n0) > (2 \uparrow\uparrow)^{2^{2^{32}+1}-2}2</math> and <math>f^{n}(0) > 2 \uparrow\uparrow 2n</math>
Line 43: Line 85:


<math>f^{g^{n1}(n0)}(0) > 2 \uparrow\uparrow\uparrow 2^{2^{32}+1}</math>
<math>f^{g^{n1}(n0)}(0) > 2 \uparrow\uparrow\uparrow 2^{2^{32}+1}</math>
or, for a more precise lower bound:
<math>g^{n1}(n0) > (2 \uparrow\uparrow)^{2^{2^{32}+1}-4}2^{2^{2^{32}}}</math>
<math>f^{g^{n1}(n0)}(0) > f^{(2 \uparrow\uparrow)^{2^{2^{32}+1}-4}2^{2^{2^{32}}}}(0) > 2 \uparrow\uparrow (2 \times (2 \uparrow\uparrow)^{2^{2^{32}+1}-4}2^{2^{2^{32}}}) > 2\uparrow\uparrow (2 \uparrow\uparrow)^{2^{2^{32}+1}-4}2^{2^{2^{32}}} => (2  \uparrow\uparrow)^{2^{2^{32}+1}-3}2^{2^{2^{32}}}</math>
<math>f^{g^{n1}(n0)}(0) > (2 \uparrow\uparrow)^{2^{2^{32}+1}-3}2^{2^{2^{32}}}</math>
'''Upper bound'''
<math>g^{n1}(n0) < (2 \uparrow\uparrow)^{2^{2^{32}+1}-3}7</math> and <math>f^{n}(0) < 2 \uparrow\uparrow 3n</math>
<math>f^{g^{n1}(n0)}(0) < 2 \uparrow\uparrow (3 \times (2 \uparrow\uparrow)^{2^{2^{32}+1}-3}7) < 2 \uparrow\uparrow (2 \uparrow\uparrow)^{2^{2^{32}+1}-3}8 => (2 \uparrow\uparrow)^{2^{2^{32}+1}-2}8</math>
<math>g^{n1}(n0) < (2 \uparrow\uparrow)^{2^{2^{32}+1}-2}8</math>
or, for a more precise upper bound:
<math>g^{n1}(n0) < (2 \uparrow\uparrow)^{2^{2^{32}+1}-4}(2^{2^{2^{33}}})</math> and <math>f^{n}(0) < 2 \uparrow\uparrow 3n</math>
<math>f^{g^{n1}(n0)}(0) < 2 \uparrow\uparrow (3 \times (2 \uparrow\uparrow)^{2^{2^{32}+1}-4}(2^{2^{2^{33}}})) < 2 \uparrow\uparrow (2 \uparrow\uparrow)^{2^{2^{32}+1}-4}(2^{2^{2^{33}}}+1) => (2 \uparrow\uparrow)^{2^{2^{32}+1}-3}(2^{2^{2^{33}}}+1)</math>
<math>f^{g^{n1}(n0)}(0) < (2 \uparrow\uparrow)^{2^{2^{32}+1}-3}(2^{2^{2^{33}}}+1)</math>
or, for an even more precise upper bound:
<math>g^{n1}(n0) < (2 \uparrow\uparrow)^{2^{2^{32}+1}-4}(2^{2^{2^{32}+2}})</math> and <math>f^{n}(0) < 2 \uparrow\uparrow 3n</math>
<math>f^{g^{n1}(n0)}(0) < 2 \uparrow\uparrow (3 \times (2 \uparrow\uparrow)^{2^{2^{32}+1}-4}(2^{2^{2^{32}+2}})) < 2 \uparrow\uparrow (2 \uparrow\uparrow)^{2^{2^{32}+1}-4}(2^{2^{2^{32}+2}}+1) => (2 \uparrow\uparrow)^{2^{2^{32}+1}-3}(2^{2^{2^{32}+2}}+1)</math>
<math>f^{g^{n1}(n0)}(0) < (2 \uparrow\uparrow)^{2^{2^{32}+1}-3}(2^{2^{2^{32}+2}}+1)</math>
==Lower bound on Σ==
==Lower bound on Σ==
Σ = <math>5 \times 2^{2^{f^{g^{n1}(n0)}(0)+1}+2}+7 > 5 \times 2^{2^{(2 \uparrow\uparrow\uparrow 2^{2^{32}+1})+1}+2}+7 > 2 \uparrow\uparrow\uparrow 2^{2^{32}+1}</math>
Σ = <math>5 \times 2^{2^{f^{g^{n1}(n0)}(0)+1}+2}+7 > 5 \times 2^{2^{(2 \uparrow\uparrow\uparrow 2^{2^{32}+1})+1}+2}+7 > 2 \uparrow\uparrow\uparrow 2^{2^{32}+1}</math>


Σ > <math>2 \uparrow\uparrow\uparrow 2^{2^{32}+1}</math>
Σ > <math>2 \uparrow\uparrow\uparrow 2^{2^{32}+1}</math>
or, for a more precise lower bound:
Σ = <math>5 \times 2^{2^{f^{g^{n1}(n0)}(0)+1}+2}+7 > 2^{2^{(2 \uparrow\uparrow)^{2^{2^{32}+1}-3}2^{2^{2^{32}}}}} > (2 \uparrow\uparrow)^{2^{2^{32}+1}-3}2^{2^{2^{32}}}</math>
Σ > <math>(2 \uparrow\uparrow)^{2^{2^{32}+1}-3}2^{2^{2^{32}}}</math>
'''Upper bound'''
Σ = <math>5 \times 2^{2^{f^{g^{n1}(n0)}(0)+1}+2}+7 < 5 \times 2^{2^{((2 \uparrow\uparrow)^{2^{2^{32}+1}-2}8)+1}+2}+7 < 2^{2^{2^{(2 \uparrow\uparrow)^{2^{2^{32}+1}-2}8}}} < (2 \uparrow\uparrow)^{2^{2^{32}+1}-2}9 < (2 \uparrow\uparrow)^{2^{2^{32}+1}-2}65536 => (2 \uparrow\uparrow)^{2^{2^{32}+1}-2}2 \uparrow\uparrow 4 => (2 \uparrow\uparrow)^{2^{2^{32}+1}-1}4</math>
<math>(2 \uparrow\uparrow)^{2^{2^{32}+1}-1}4 => (2 \uparrow\uparrow)^{2^{2^{32}+1}-1}2 \uparrow\uparrow 2 => (2 \uparrow\uparrow)^{2^{2^{32}+1}}2 => (2 \uparrow\uparrow)^{2^{2^{32}+1}}2 \uparrow\uparrow 1 => (2 \uparrow\uparrow)^{2^{2^{32}+1}+1}1 => 2 \uparrow\uparrow\uparrow (2^{2^{32}+1}+1)</math>
Σ < <math>2 \uparrow\uparrow\uparrow (2^{2^{32}+1}+1)</math>
or, for a more precise upper bound:
Σ = <math>5 \times 2^{2^{f^{g^{n1}(n0)}(0)+1}+2}+7 < 2^{2^{2^{(2 \uparrow\uparrow)^{2^{2^{32}+1}-3}(2^{2^{2^{33}}}+1)}}} < (2 \uparrow\uparrow)^{2^{2^{32}+1}-3}(2^{2^{2^{33}}}+2)</math>
Σ < <math>(2 \uparrow\uparrow)^{2^{2^{32}+1}-3}(2^{2^{2^{33}}}+2)</math>
or, for an even more precise upper bound:
Σ = <math>5 \times 2^{2^{f^{g^{n1}(n0)}(0)+1}+2}+7 < 2^{2^{2^{(2 \uparrow\uparrow)^{2^{2^{32}+1}-3}(2^{2^{2^{32}+2}}+1)}}} < (2 \uparrow\uparrow)^{2^{2^{32}+1}-3}(2^{2^{2^{32}+2}}+2)</math>
Σ < <math>(2 \uparrow\uparrow)^{2^{2^{32}+1}-3}(2^{2^{2^{32}+2}}+2)</math>
=General bound on Σ=
<math>2 \uparrow\uparrow\uparrow 2^{2^{32}+1}</math> < '''Σ''' < <math>2 \uparrow\uparrow\uparrow (2^{2^{32}+1}+1)</math>
More precisely: <math>(2 \uparrow\uparrow)^{2^{2^{32}+1}-2}6</math> < '''Σ''' < <math>(2 \uparrow\uparrow)^{2^{2^{32}+1}-2}7</math>
Even more precisely: <math>(2 \uparrow\uparrow)^{2^{2^{32}+1}-2}6 < (2 \uparrow\uparrow)^{2^{2^{32}+1}-3}2^{2^{2^{32}}}</math> < '''Σ''' < <math>(2 \uparrow\uparrow)^{2^{2^{32}+1}-3}(2^{2^{2^{32}+2}}+2) < (2 \uparrow\uparrow)^{2^{2^{32}+1}-3}(2^{2^{2^{33}}}+2) < (2 \uparrow\uparrow)^{2^{2^{32}+1}-2}7</math>

Latest revision as of 15:08, 18 August 2025

Machine: 0RB1RZ0RB_1RC1LB2LB_1LB2RD1LC_1RA2RC0LD (bbch)

Better lower bound for BB(4,3)

Definitions

f(n)=22n+1

g(n)=5×22fn(0)+1+2−89

n0=5×22232+1+1−49

n1=2232+1−4

Σ = 5×22fgn1(n0)(0)+1+2+7

Lower bound on f^n(0)

f(n)=22n+1

f(0)=221;f(f(0))=22(221+1)>(2↑)41;f3(0)=22(22(221+1)+1)>(2↑)61

fk(0)=22fk−1(0)+1>22fk−1(0)=>(2↑)2fk−1(0)=>(2↑)2afk−a(0)

=>fk(0)>(2↑)2k1=2↑↑2k

=>fn(0)>2↑↑2n

Upper bound

fu(n)=222n;fu(0)=222;fu0(0)=1

fu(n)>f(n) as 2n>n+1

fuk(0)=(2↑)3fuk−1(0)

fu2(0)=fu(222)=222222=>(2↑)61

fuk(0)=(2↑)3k1=2↑↑3k;fu(n)>f(n)=>2↑↑3k>f(n)

fn(0)<2↑↑3n

Lower bound on g^k(n)

g(n)=5×22fn(0)+1+2−89>5×222↑↑2n+2−89>222↑↑2n=2↑↑(2n+2)

g2(n)>5×22f2↑↑(2n+2)(0)+1+2−89>5×222↑↑2↑↑(2n+2)+2−89>2↑↑2↑↑(2n+2)

gk(n)>2↑↑(2×gk−1(n)+2)=(2↑↑)1(2×gk−1(n)+2)=>>(2↑↑)a(2×gk−a(n)+2)

gk(n)>(2↑↑)k(2n+2)>(2↑↑)k2n

Upper bound

g(n)=5×22fn(0)+1+2−89<5×22(2↑↑3n)+1+2−89<5×22(2↑↑3n)+1+2<2↑↑(3n+3)

g2(n)<2↑↑(3×(2↑↑(3n+3))+3)<2↑↑2↑↑(3n+4)

gk(n)<2↑↑(3×(gk−1(n))+3)<2↑↑2↑gk−1(n)

gk(n)<(2↑↑)k(3n+k+2)

Lower bound on g^n1(n0)

gn1(n0)=g2232+1−4(5×22232+1+1−49)>g2232+1−4(22232)>(2↑↑)2232+1−422232 ; Note that 2↑↑6<22232<2↑↑7

(2↑↑)2232+1−422232>(2↑↑)2232+1−42↑↑6=>(2↑↑)2232+1−36>(2↑↑)2232+1−34=>(2↑↑)2232+1−32↑↑2=>(2↑↑)2232+1−22

gn1(n0)>(2↑↑)2232+1−22

Upper bound

gn1(n0)=g2232+1−4(5×22232+1+1−49)<(2↑↑)2232+1−4(3×(5×22232+1+1−49)+2232+1−4+2)<(2↑↑)2232+1−42↑↑7=>(2↑↑)2232+1−37

gn1(n0)<(2↑↑)2232+1−37

or, for a more precise upper bound:

gn1(n0)=g2232+1−4(5×22232+1+1−49)<(2↑↑)2232+1−4(3×(5×22232+1+1−49)+2232+1−4+2)<(2↑↑)2232+1−4(22233)

gn1(n0)<(2↑↑)2232+1−4(22233)

or, for an even more precise upper bound:

(2↑↑)2232+1−4(3×(5×22232+1+1−49)+2232+1−4+2)<(2↑↑)2232+1−4(22232+2)

gn1(n0)<(2↑↑)2232+1−4(22232+2)

Lower bound on f^g^n1(n0)(0)

gn1(n0)>(2↑↑)2232+1−22 and fn(0)>2↑↑2n

fgn1(n0)(0)>f(2↑↑)2232+1−22(0)>2↑↑(2×(2↑↑)2232+1−22)>2↑↑(2↑↑)2232+1−22=>(2↑↑)2232+1−12

(2↑↑)2232+1−12=>(2↑↑)2232+1−12↑↑1=>(2↑↑)2232+11=>2↑↑↑2232+1

fgn1(n0)(0)>2↑↑↑2232+1

or, for a more precise lower bound:

gn1(n0)>(2↑↑)2232+1−422232

fgn1(n0)(0)>f(2↑↑)2232+1−422232(0)>2↑↑(2×(2↑↑)2232+1−422232)>2↑↑(2↑↑)2232+1−422232=>(2↑↑)2232+1−322232

fgn1(n0)(0)>(2↑↑)2232+1−322232

Upper bound

gn1(n0)<(2↑↑)2232+1−37 and fn(0)<2↑↑3n

fgn1(n0)(0)<2↑↑(3×(2↑↑)2232+1−37)<2↑↑(2↑↑)2232+1−38=>(2↑↑)2232+1−28

gn1(n0)<(2↑↑)2232+1−28

or, for a more precise upper bound:

gn1(n0)<(2↑↑)2232+1−4(22233) and fn(0)<2↑↑3n

fgn1(n0)(0)<2↑↑(3×(2↑↑)2232+1−4(22233))<2↑↑(2↑↑)2232+1−4(22233+1)=>(2↑↑)2232+1−3(22233+1)

fgn1(n0)(0)<(2↑↑)2232+1−3(22233+1)

or, for an even more precise upper bound:

gn1(n0)<(2↑↑)2232+1−4(22232+2) and fn(0)<2↑↑3n

fgn1(n0)(0)<2↑↑(3×(2↑↑)2232+1−4(22232+2))<2↑↑(2↑↑)2232+1−4(22232+2+1)=>(2↑↑)2232+1−3(22232+2+1)

fgn1(n0)(0)<(2↑↑)2232+1−3(22232+2+1)

Lower bound on Σ

Σ = 5×22fgn1(n0)(0)+1+2+7>5×22(2↑↑↑2232+1)+1+2+7>2↑↑↑2232+1

Σ > 2↑↑↑2232+1

or, for a more precise lower bound:

Σ = 5×22fgn1(n0)(0)+1+2+7>22(2↑↑)2232+1−322232>(2↑↑)2232+1−322232

Σ > (2↑↑)2232+1−322232

Upper bound

Σ = 5×22fgn1(n0)(0)+1+2+7<5×22((2↑↑)2232+1−28)+1+2+7<222(2↑↑)2232+1−28<(2↑↑)2232+1−29<(2↑↑)2232+1−265536=>(2↑↑)2232+1−22↑↑4=>(2↑↑)2232+1−14

(2↑↑)2232+1−14=>(2↑↑)2232+1−12↑↑2=>(2↑↑)2232+12=>(2↑↑)2232+12↑↑1=>(2↑↑)2232+1+11=>2↑↑↑(2232+1+1)

Σ < 2↑↑↑(2232+1+1)

or, for a more precise upper bound:

Σ = 5×22fgn1(n0)(0)+1+2+7<222(2↑↑)2232+1−3(22233+1)<(2↑↑)2232+1−3(22233+2)

Σ < (2↑↑)2232+1−3(22233+2)

or, for an even more precise upper bound:

Σ = 5×22fgn1(n0)(0)+1+2+7<222(2↑↑)2232+1−3(22232+2+1)<(2↑↑)2232+1−3(22232+2+2)

Σ < (2↑↑)2232+1−3(22232+2+2)

General bound on Σ

2↑↑↑2232+1 < Σ < 2↑↑↑(2232+1+1)

More precisely: (2↑↑)2232+1−26 < Σ < (2↑↑)2232+1−27

Even more precisely: (2↑↑)2232+1−26<(2↑↑)2232+1−322232 < Σ < (2↑↑)2232+1−3(22232+2+2)<(2↑↑)2232+1−3(22233+2)<(2↑↑)2232+1−27

Retrieved from "https://wiki.bbchallenge.org/w/index.php?title=User:Polygon/Better_lower_bound_for_BB(4,3)&oldid=3261"