RAM-to-TM time-class containment -- definitions

This layer fixes the twenty-work-tape concrete simulator and packages its fourth-degree resource envelope as a natural polynomial.

def Complexity.RAM.RegisterStore.Machine.standardControlInstructionTapes : ControlInstructionTapes 19

The canonical assignment of the eighteen data roles and one disjoint program-counter role. The complete decision simulator adds one buffer tape, so the resulting TM has twenty work tapes.

Equations

• One or more equations did not get rendered due to their size.

noncomputable def Complexity.RAM.RegisterStore.Machine.programDecisionPolynomial (program : Program) (p : Polynomial ℕ) : Polynomial ℕ

Polynomial obtained by substituting a polynomial RAM-time bound into the checked concrete simulation envelope.

Equations

• One or more equations did not get rendered due to their size.