BinaryMachine

Navigation page for Blueprint/D5/S0/Computability/BinaryMachine/ at upstream snapshot 4410c929602bdd76857e5da92ed3bb9f99a6f233.

Contents

• Total normalization of bounded verifiers
• Complexity classes in one concrete machine model
• Uniform numerical clocks and output bounds
• Executed polynomial transducer composition
• Polynomial preprocessing before a total verifier
• Both tape decisions in a stack frame
• Finite binary tape machines
• Exact transition count of machine 3626
• NP preimages with exact target witness bounds
• An executed ordered pair constructor
• Preserving witnesses under polynomial instance maps
• Total exact binary pair projections
• Numerical polynomial envelopes
• Composition of polynomial many-one reductions
• A total primitive witness-length comparison
• Whole stack programs as polynomial tape machines
• Physical tape insertion and deletion
• Decision continuations and exact word movement
• Boolean register regions on a tape
• Register injection and disjoint frames
• Initialization of encoded Boolean registers
• Finite Boolean stack machines
• Exact total ordered pair decoding
• Primitive unary-prefix parsing
• Physical stack deletion
• Executed unary polynomial budgets
• Finite program algebra and compilation
• Counted stack-to-tape simulation
• Executed word operations
• Blank-padding equivalence of tape execution
• Tape execution inside finite stacks
• Polynomial pairing from one common input
• Unary outer-length prefixes
• Checking the original target certificate bound