caTimeBound
Defines the target runtime bound for a cellular automaton model M on input size n as the existence of positive constant c such that grid side length times logical depth is at most c times n to the one-third times log of n plus two. Complexity researchers embedding SAT instances into Recognition Science CA models would cite this when deriving simulation costs. The definition directly packages the Theta of n to the one-third side length assumption together with the logarithmic depth formula into a single scaling inequality.
claimLet $M$ be a runtime model whose side length function $s(n)$ satisfies $c_1 n^{1/3} < s(n) < c_2 n^{1/3}$ for positive constants $c_1, c_2$. Let $d(n) = $ ceil of log base 2 of $n+1$. The bound holds when there exists $c > 0$ such that $s(n) · d(n) ≤ c · n^{1/3} · log(n+2)$.
background
CARuntimeModel packages the abstract assumptions for embedding SAT into a cellular automaton: it supplies a side length function from n to natural numbers together with the explicit hypothesis that this length is Theta of n to the one-third, plus a locality proposition stating that constraints are realized by constant-diameter gadgets. logicalDepth is defined as the ceiling of log base 2 of n plus one, which is O of log n and represents the number of implication layers in the recognition propagation. The module sets the local theoretical setting as abstract runtime parameters for the CA embedding, drawing on upstream cost functions from multiplicative recognizers and observer forcing to ground the J-cost interpretation of recognition events.
proof idea
This is a direct definition that asserts the existence of scaling constant c making the product of side length and logical depth obey the stated inequality. It combines the sideLength_bound hypothesis inside CARuntimeModel with the explicit formula for logicalDepth to produce the O of n to the one-third log n target.
why it matters in Recognition Science
This definition supplies the concrete runtime target used in subsequent propositions on CA to TM simulation costs and three-SAT runtime bounds within the module. It connects the abstract CA embedding to Recognition Science complexity analysis by enforcing the n to the one-third log n scaling that arises from three-dimensional locality and logarithmic propagation depth. The bound aligns with the eight-tick octave and D equals 3 spatial dimensions in the forcing chain by treating the grid as a three-dimensional recognition manifold.
scope and limits
- Does not prove that any concrete cellular automaton satisfies the side length bound.
- Does not compute or bound the explicit value of the constant c.
- Does not incorporate the locality assumption into the numerical inequality.
- Does not address the simulation overhead when mapping the CA to a Turing machine.
formal statement (Lean)
27def caTimeBound (M : CARuntimeModel) (n : ℕ) : Prop :=
proof body
Definition body.
28 ∃ c : ℝ, 0 < c ∧ (M.sideLength n : ℝ) * (logicalDepth n : ℝ) ≤ c * (n : ℝ)^(1/3 : ℝ) * Real.log (n + 2)
29
30/-- CA→TM simulation cost: TM time = O(volume * steps).
31 The actual content would specify that a Turing Machine can simulate
32 a cellular automaton with volume V and time T in O(V·T) steps. -/