Sequences - Revision history

Coda: /* Π1 */ add OEIS link to BB_clean instead

2025-10-23T15:12:08Z

Π1: add OEIS link to BB_clean instead

← Older revision		Revision as of 15:12, 23 October 2025
Line 80:		Line 80:
	\|The maximum number of steps that an n-state 2-symbol Turing machine can make on an initially blank tape until it halts on a blank tape		\|The maximum number of steps that an n-state 2-symbol Turing machine can make on an initially blank tape until it halts on a blank tape
	\|(see comments #75 and #77 [https://scottaaronson.blog/?p=5661 here])		\|(see comments #75 and #77 [https://scottaaronson.blog/?p=5661 here])
	\|		\|[[oeis:A119683\|A119683]]
	\|-		\|-
	\|BB_ones		\|BB_ones
Line 134:		Line 134:
	\|see [[Busy Beaver for lambda calculus#Champions]]		\|see [[Busy Beaver for lambda calculus#Champions]]
	\|[[oeis:A333479\|A333479]]		\|[[oeis:A333479\|A333479]]
	\|-
	\|
	\|
	~~\|Maximal number of steps that an n-state Turing machine can make which was started on an initially blank tape before halting on the blank tape again.~~
	\|
	~~\|[[oeis:A119683\|A119683]]~~
	\|-		\|-
	\|}		\|}

Coda: /* Π1 */ Add noncomputable sequence (starting and ending with blank tape)

2025-10-23T15:09:37Z

Π1: Add noncomputable sequence (starting and ending with blank tape)

← Older revision		Revision as of 15:09, 23 October 2025
Line 134:		Line 134:
	\|see [[Busy Beaver for lambda calculus#Champions]]		\|see [[Busy Beaver for lambda calculus#Champions]]
	\|[[oeis:A333479\|A333479]]		\|[[oeis:A333479\|A333479]]
			\|-
			\|
			\|
			\|Maximal number of steps that an n-state Turing machine can make which was started on an initially blank tape before halting on the blank tape again.
			\|
			\|[[oeis:A119683\|A119683]]
	\|-		\|-
	\|}		\|}

Polygon: /* Π1 */ Added Maximum Consecutive Ones Function

2025-10-17T14:14:16Z

Π1: Added Maximum Consecutive Ones Function

← Older revision		Revision as of 14:14, 17 October 2025
Line 86:		Line 86:
	\|The maximum number of 1's that an n-state 2-symbol Turing machine can make in a row, before halting on a 0 next to it		\|The maximum number of 1's that an n-state 2-symbol Turing machine can make in a row, before halting on a 0 next to it
	\|		\|
			\|
			\|-
			\|[[Maximum Consecutive Ones Function]]
			\|num(n)
			\|The maximum amount of consecutive 1's that an n-state 2-symbol Turing machine can print before eventually halting
			\|see [[Maximum Consecutive Ones Function]]
	\|		\|
	\|-		\|-

Polygon: /* Π1 */ No oeis

2025-09-26T17:01:26Z

Π1: No oeis

← Older revision		Revision as of 17:01, 26 September 2025
Line 115:		Line 115:
	\|Maximum number of steps that an n-instruction Turing machine can take from a blank tape before halting, where the Turing machines first n-1 instructions are a machine which runs for gBBi(n-1) steps.		\|Maximum number of steps that an n-instruction Turing machine can take from a blank tape before halting, where the Turing machines first n-1 instructions are a machine which runs for gBBi(n-1) steps.
	\|see [[Instruction-Limited Busy Beaver#Instruction-Limited Busy Beaver Variants]]		\|see [[Instruction-Limited Busy Beaver#Instruction-Limited Busy Beaver Variants]]
	\|		\| -
	\|-		\|-
	\|[[Instruction-Limited Busy Beaver#Instruction-Limited Busy Beaver Variants\|Instruction-Limited Blanking Busy Beaver]]		\|[[Instruction-Limited Busy Beaver#Instruction-Limited Busy Beaver Variants\|Instruction-Limited Blanking Busy Beaver]]
Line 121:		Line 121:
	\|Maximum number of steps that an n-instruction Turing machine (allowing any number of states and symbols) can take on an initially blank tape before blanking the tape again.		\|Maximum number of steps that an n-instruction Turing machine (allowing any number of states and symbols) can take on an initially blank tape before blanking the tape again.
	\|see [[Instruction-Limited Busy Beaver#Instruction-Limited Busy Beaver Variants]]		\|see [[Instruction-Limited Busy Beaver#Instruction-Limited Busy Beaver Variants]]
	\|		\| -
	\|-		\|-
	\|[[Busy Beaver for lambda calculus]]		\|[[Busy Beaver for lambda calculus]]

Polygon: /* Noncomputable Sequences */ Added links to some instruction-limited functions

2025-09-26T16:57:07Z

Noncomputable Sequences: Added links to some instruction-limited functions

← Older revision		Revision as of 16:57, 26 September 2025
Line 105:		Line 105:
	\|[[oeis:A384629\|A384629]]		\|[[oeis:A384629\|A384629]]
	\|-		\|-
	\|Instruction-Limited Symbol Busy Beaver		\|[[Instruction-Limited Busy Beaver\|Instruction-Limited Symbol Busy Beaver]]
	\|Σi(n)		\|Σi(n)
	\|Maximum number of non-blank symbols that an n-instruction Turing machine (allowing any number of states and symbols) can leave on an initially blank tape before eventually halting.		\|Maximum number of non-blank symbols that an n-instruction Turing machine (allowing any number of states and symbols) can leave on an initially blank tape before eventually halting.
Line 111:		Line 111:
	\|[[oeis:A384766\|A384766]]		\|[[oeis:A384766\|A384766]]
	\|-		\|-
	\|Instruction-Limited Greedy Busy Beaver		\|[[Instruction-Limited Busy Beaver#Instruction-Limited Busy Beaver Variants\|Instruction-Limited Greedy Busy Beaver]]
	\|gBBi(n)		\|gBBi(n)
	\|Maximum number of steps that an n-instruction Turing machine can take from a blank tape before halting, where the Turing machines first n-1 instructions are a machine which runs for gBBi(n-1) steps.		\|Maximum number of steps that an n-instruction Turing machine can take from a blank tape before halting, where the Turing machines first n-1 instructions are a machine which runs for gBBi(n-1) steps.
Line 117:		Line 117:
	\|		\|
	\|-		\|-
	\|Instruction-Limited Blanking Busy Beaver		\|[[Instruction-Limited Busy Beaver#Instruction-Limited Busy Beaver Variants\|Instruction-Limited Blanking Busy Beaver]]
	\|BLBi(n)		\|BLBi(n)
	\|Maximum number of steps that an n-instruction Turing machine (allowing any number of states and symbols) can take on an initially blank tape before blanking the tape again.		\|Maximum number of steps that an n-instruction Turing machine (allowing any number of states and symbols) can take on an initially blank tape before blanking the tape again.

Polygon: /* Π1 */ Added Instruction-Limited greedy Busy Beaver

2025-09-25T18:29:55Z

Π1: Added Instruction-Limited greedy Busy Beaver

← Older revision		Revision as of 18:29, 25 September 2025
Line 110:		Line 110:
	\|see [[Instruction-Limited Busy Beaver#Champions]]		\|see [[Instruction-Limited Busy Beaver#Champions]]
	\|[[oeis:A384766\|A384766]]		\|[[oeis:A384766\|A384766]]
			\|-
			\|Instruction-Limited Greedy Busy Beaver
			\|gBBi(n)
			\|Maximum number of steps that an n-instruction Turing machine can take from a blank tape before halting, where the Turing machines first n-1 instructions are a machine which runs for gBBi(n-1) steps.
			\|see [[Instruction-Limited Busy Beaver#Instruction-Limited Busy Beaver Variants]]
			\|
	\|-		\|-
	\|Instruction-Limited Blanking Busy Beaver		\|Instruction-Limited Blanking Busy Beaver

Polygon: Added BLBi(n) and a link for BB_lambda1 values

2025-09-22T17:48:18Z

Added BLBi(n) and a link for BB_lambda1 values

← Older revision		Revision as of 17:48, 22 September 2025
Line 110:		Line 110:
	\|see [[Instruction-Limited Busy Beaver#Champions]]		\|see [[Instruction-Limited Busy Beaver#Champions]]
	\|[[oeis:A384766\|A384766]]		\|[[oeis:A384766\|A384766]]
			\|-
			\|Instruction-Limited Blanking Busy Beaver
			\|BLBi(n)
			\|Maximum number of steps that an n-instruction Turing machine (allowing any number of states and symbols) can take on an initially blank tape before blanking the tape again.
			\|see [[Instruction-Limited Busy Beaver#Instruction-Limited Busy Beaver Variants]]
			\|
	\|-		\|-
	\|[[Busy Beaver for lambda calculus]]		\|[[Busy Beaver for lambda calculus]]
Line 135:		Line 141:
	\|BBλ<sub>1</sub>		\|BBλ<sub>1</sub>
	\|Maximum beta/oracle normal form size of any 1-closed lambda term of size n.		\|Maximum beta/oracle normal form size of any 1-closed lambda term of size n.
	\|		\|see [[Busy Beaver for lambda calculus#Oracle Busy Beaver]]
	\|[[oeis:A385712\|A385712]]		\|[[oeis:A385712\|A385712]]
	\|}		\|}
Line 150:		Line 156:
	\|BBBB(n)		\|BBBB(n)
	\|		\|
	\|~~See~~ [[Beeping Busy Beaver#Beeping Booping Busy Beavers]]		\|see [[Beeping Busy Beaver#Beeping Booping Busy Beavers]]
	\|}		\|}

Polygon: /* Π3 */ Added a link to values of BBBB

2025-09-22T17:37:43Z

Π3: Added a link to values of BBBB

← Older revision		Revision as of 17:37, 22 September 2025
Line 150:		Line 150:
	\|BBBB(n)		\|BBBB(n)
	\|		\|
	\|~~BBBB(1) = 1~~		\|See [[Beeping Busy Beaver#Beeping Booping Busy Beavers]]
	\|}		\|}

Int-y1: add BBλ_1, move BBBB to Π3

2025-09-22T03:32:35Z

add BBλ_1, move BBBB to Π3

@@ Line 131: / Line 131: @@
 |The latest possible step that any 2-symbol TM with n states exits a chosen state finitely many times
 |see [[Beeping Busy Beaver#Results]]
 |-
 |[[Beeping Busy Beaver#Beeping Booping Busy Beavers|Beeping Booping busy beaver]]

Int-y1: link

2025-09-21T23:06:15Z

link

← Older revision		Revision as of 23:06, 21 September 2025
Line 111:		Line 111:
	\|[[oeis:A384766\|A384766]]		\|[[oeis:A384766\|A384766]]
	\|-		\|-
	\|Busy Beaver for lambda calculus		\|[[Busy Beaver for lambda calculus]]
	\|BBλ(n)		\|BBλ(n)
	\|Maximum beta normal form size of any closed lambda term of size n.		\|Maximum beta normal form size of any closed lambda term of size n.