Extension by arbitrary unused catalyst bits
DefinitionCatalyticTreeEval_PrefixExtensionExtend a native configuration by appending arbitrary bits beyond its current catalyst. The control state, all three heads, work tape and existing output are unchanged. Step and trajectory preservation under a strict prefix bound are subsequent proof obligations.
Definition code
import Definitions.Def_CatalyticTreeEval_MachineContracts
set_option autoImplicit false
namespace CatalyticTreeEval.Contracts.PrefixExtension
open CatalyticMatching.General
/-- Add untouched arbitrary bits beyond a configuration's current catalyst. -/
def extend {M : Machine} (suffix : List Bool) (c : Configuration M) : Configuration M :=
{ c with catalyst := c.catalyst ++ suffix }
end CatalyticTreeEval.Contracts.PrefixExtension
Source
Henzinger, Pyne and Ragavan, Catalytic Tree Evaluation from Matching Vectors, https://arxiv.org/html/2602.14320v3, Section 3 machine model and Corollary 4.2.