Documentation

Complexitylib.Models.TuringMachine.Subroutines.BinaryRippleSub.Internal.Out

Linear-time canonical binary subtraction -- output discipline #

The borrow scan, backward cleanup, and operand rewinds leave the public output tape one-way, so the core and complete machines are safe transducers.

theorem Complexity.TM.binaryRippleSubCoreTM_isTransducer_internal {n : } (lhsIdx rhsIdx resultIdx : Fin n) :
(binaryRippleSubCoreTM lhsIdx rhsIdx resultIdx).IsTransducer

The direct subtraction core never moves the public output head left.

theorem Complexity.TM.binaryRippleSubTM_isTransducer_internal {n : } (lhsIdx rhsIdx resultIdx : Fin n) :
(binaryRippleSubTM lhsIdx rhsIdx resultIdx).IsTransducer

Backward canonicalization followed by both operand rewinds remains a transducer.