Documentation

LeanPool.GapCVP.Part03F

GapCVP proof, part 03, continuation 06 #

@[reducible, inline]

Lifts each old-machine step outside the specialized comparison phase.

Equations
  • One or more equations did not get rendered due to their size.
Instances For
    def GapCVP.CNFEncodedClauseSort.DelimitedCompareTrace.cleanup (chosenStep : delimitedPairComparisonMachine.CfgOption delimitedPairComparisonMachine.Cfg) (lift : NonComparisonStepLift chosenStep) (outcome : EncodedWordOrdering) (input firstCounter firstReversed secondCounter secondReversed firstForward secondForward source sourcePrefix output : List Bool) :
    StateTransition.EvalsToInTime chosenStep (delimitedCompareConfiguration 7 outcome input firstCounter firstReversed secondCounter secondReversed firstForward secondForward source sourcePrefix output) (some (delimitedCompareConfiguration 8 outcome input [] [] [] [] [] [] source sourcePrefix output)) (firstCounter.length + firstReversed.length + secondCounter.length + secondReversed.length + firstForward.length + secondForward.length + 1)

    Clears the six comparison work tapes using any compatible machine step.

    Equations
    • One or more equations did not get rendered due to their size.
    Instances For
      def GapCVP.CNFEncodedClauseSort.DelimitedCompareTrace.trailing (chosenStep : delimitedPairComparisonMachine.CfgOption delimitedPairComparisonMachine.Cfg) (lift : NonComparisonStepLift chosenStep) (outcome : EncodedWordOrdering) (input source sourcePrefix output : List Bool) :
      StateTransition.EvalsToInTime chosenStep (delimitedCompareConfiguration 8 outcome input [] [] [] [] [] [] source sourcePrefix output) (some (delimitedCompareConfiguration 9 outcome [] [] [] [] [] [] [] (input.reverse ++ source) (List.replicate input.length true ++ sourcePrefix) output)) (input.length + 1)

      Restores the trailing input using any compatible machine step.

      Equations
      • One or more equations did not get rendered due to their size.
      Instances For
        def GapCVP.CNFEncodedClauseSort.DelimitedCompareTrace.source (chosenStep : delimitedPairComparisonMachine.CfgOption delimitedPairComparisonMachine.Cfg) (lift : NonComparisonStepLift chosenStep) (outcome : EncodedWordOrdering) (source sourcePrefix output : List Bool) :
        StateTransition.EvalsToInTime chosenStep (delimitedCompareConfiguration 10 outcome [] [] [] [] [] [] [] source sourcePrefix output) (some (delimitedCompareConfiguration 11 outcome [] [] [] [] [] [] [] [] sourcePrefix (false :: (source.reverse ++ output)))) (source.length + 1)

        Restores the saved source using any compatible machine step.

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

          Restores prefix markers and halts using any compatible machine step.

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

            GapCVP reduction support.

            Equations
            • One or more equations did not get rendered due to their size.
            Instances For
              noncomputable def GapCVP.CNFEncodedClauseSort.DelimitedCompareTrace.finish (chosenStep : delimitedPairComparisonMachine.CfgOption delimitedPairComparisonMachine.Cfg) (lift : NonComparisonStepLift chosenStep) (outcome : EncodedWordOrdering) (input firstCounter firstReversed secondCounter secondReversed firstForward secondForward source sourcePrefix output : List Bool) :
              StateTransition.EvalsToInTime chosenStep (delimitedCompareConfiguration 7 outcome input firstCounter firstReversed secondCounter secondReversed firstForward secondForward source sourcePrefix output) (some (Turing.haltList delimitedPairComparisonMachine (delimitedCompareRestoredWord outcome input source sourcePrefix output))) (firstCounter.length + firstReversed.length + secondCounter.length + secondReversed.length + firstForward.length + secondForward.length + 3 * input.length + source.length + sourcePrefix.length + 5)

              Restores every saved tape and halts using any compatible machine step.

              Equations
              • One or more equations did not get rendered due to their size.
              Instances For
                noncomputable def GapCVP.CNFEncodedClauseSort.delimitedCompareFinishTrace (outcome : EncodedWordOrdering) (input firstCounter firstReversed secondCounter secondReversed firstForward secondForward source sourcePrefix output : List Bool) :
                StateTransition.EvalsToInTime delimitedPairComparisonMachine.step (delimitedCompareConfiguration 7 outcome input firstCounter firstReversed secondCounter secondReversed firstForward secondForward source sourcePrefix output) (some (Turing.haltList delimitedPairComparisonMachine (delimitedCompareRestoredWord outcome input source sourcePrefix output))) (firstCounter.length + firstReversed.length + secondCounter.length + secondReversed.length + firstForward.length + secondForward.length + 3 * input.length + source.length + sourcePrefix.length + 5)

                Internal support shared across GapCVP continuation modules.

                Equations
                • One or more equations did not get rendered due to their size.
                Instances For
                  def GapCVP.CNFEncodedClauseSort.DelimitedCompareTrace.firstPrefix (chosenStep : delimitedPairComparisonMachine.CfgOption delimitedPairComparisonMachine.Cfg) (lift : NonComparisonStepLift chosenStep) (outcome : EncodedWordOrdering) (count : ) (tail firstCounter firstReversed secondCounter secondReversed firstForward secondForward source sourcePrefix output : List Bool) :
                  StateTransition.EvalsToInTime chosenStep (delimitedCompareConfiguration 0 outcome (List.replicate count true ++ false :: tail) firstCounter firstReversed secondCounter secondReversed firstForward secondForward source sourcePrefix output) (some (delimitedCompareConfiguration 1 outcome tail (List.replicate count true ++ firstCounter) firstReversed secondCounter secondReversed firstForward secondForward (false :: (List.replicate count true ++ source)) (List.replicate (count + 1) true ++ sourcePrefix) output)) (count + 1)

                  Reads the first unary prefix using any compatible machine step.

                  Equations
                  • One or more equations did not get rendered due to their size.
                  Instances For
                    noncomputable def GapCVP.CNFEncodedClauseSort.delimitedCompareFirstPrefixTrace (outcome : EncodedWordOrdering) (count : ) (tail firstCounter firstReversed secondCounter secondReversed firstForward secondForward source sourcePrefix output : List Bool) :
                    StateTransition.EvalsToInTime delimitedPairComparisonMachine.step (delimitedCompareConfiguration 0 outcome (List.replicate count true ++ false :: tail) firstCounter firstReversed secondCounter secondReversed firstForward secondForward source sourcePrefix output) (some (delimitedCompareConfiguration 1 outcome tail (List.replicate count true ++ firstCounter) firstReversed secondCounter secondReversed firstForward secondForward (false :: (List.replicate count true ++ source)) (List.replicate (count + 1) true ++ sourcePrefix) output)) (count + 1)

                    Internal support shared across GapCVP continuation modules.

                    Equations
                    • One or more equations did not get rendered due to their size.
                    Instances For
                      def GapCVP.CNFEncodedClauseSort.DelimitedCompareTrace.firstMissingPrefix (chosenStep : delimitedPairComparisonMachine.CfgOption delimitedPairComparisonMachine.Cfg) (lift : NonComparisonStepLift chosenStep) (outcome : EncodedWordOrdering) (count : ) (firstCounter firstReversed secondCounter secondReversed firstForward secondForward source sourcePrefix output : List Bool) :
                      StateTransition.EvalsToInTime chosenStep (delimitedCompareConfiguration 0 outcome (List.replicate count true) firstCounter firstReversed secondCounter secondReversed firstForward secondForward source sourcePrefix output) (some (delimitedCompareConfiguration 7 EncodedWordOrdering.invalid [] (List.replicate count true ++ firstCounter) firstReversed secondCounter secondReversed firstForward secondForward (List.replicate count true ++ source) (List.replicate count true ++ sourcePrefix) output)) (count + 1)

                      Detects a missing first delimiter using any compatible machine step.

                      Equations
                      • One or more equations did not get rendered due to their size.
                      Instances For
                        noncomputable def GapCVP.CNFEncodedClauseSort.delimitedCompareFirstMissingPrefixTrace (outcome : EncodedWordOrdering) (count : ) (firstCounter firstReversed secondCounter secondReversed firstForward secondForward source sourcePrefix output : List Bool) :
                        StateTransition.EvalsToInTime delimitedPairComparisonMachine.step (delimitedCompareConfiguration 0 outcome (List.replicate count true) firstCounter firstReversed secondCounter secondReversed firstForward secondForward source sourcePrefix output) (some (delimitedCompareConfiguration 7 EncodedWordOrdering.invalid [] (List.replicate count true ++ firstCounter) firstReversed secondCounter secondReversed firstForward secondForward (List.replicate count true ++ source) (List.replicate count true ++ sourcePrefix) output)) (count + 1)

                        Internal support shared across GapCVP continuation modules.

                        Equations
                        • One or more equations did not get rendered due to their size.
                        Instances For
                          def GapCVP.CNFEncodedClauseSort.DelimitedCompareTrace.firstPartialPayload (chosenStep : delimitedPairComparisonMachine.CfgOption delimitedPairComparisonMachine.Cfg) (lift : NonComparisonStepLift chosenStep) (outcome : EncodedWordOrdering) (payload remainingCounter firstReversed secondCounter secondReversed firstForward secondForward source sourcePrefix output : List Bool) :
                          StateTransition.EvalsToInTime chosenStep (delimitedCompareConfiguration 1 outcome payload (List.replicate payload.length true ++ remainingCounter) firstReversed secondCounter secondReversed firstForward secondForward source sourcePrefix output) (some (delimitedCompareConfiguration 1 outcome [] remainingCounter (payload.reverse ++ firstReversed) secondCounter secondReversed firstForward secondForward (payload.reverse ++ source) (List.replicate payload.length true ++ sourcePrefix) output)) payload.length

                          Reads an incomplete first payload using any compatible machine step.

                          Equations
                          • One or more equations did not get rendered due to their size.
                          Instances For
                            noncomputable def GapCVP.CNFEncodedClauseSort.delimitedCompareFirstPartialPayloadTrace (outcome : EncodedWordOrdering) (payload remainingCounter firstReversed secondCounter secondReversed firstForward secondForward source sourcePrefix output : List Bool) :
                            StateTransition.EvalsToInTime delimitedPairComparisonMachine.step (delimitedCompareConfiguration 1 outcome payload (List.replicate payload.length true ++ remainingCounter) firstReversed secondCounter secondReversed firstForward secondForward source sourcePrefix output) (some (delimitedCompareConfiguration 1 outcome [] remainingCounter (payload.reverse ++ firstReversed) secondCounter secondReversed firstForward secondForward (payload.reverse ++ source) (List.replicate payload.length true ++ sourcePrefix) output)) payload.length

                            Internal support shared across GapCVP continuation modules.

                            Equations
                            • One or more equations did not get rendered due to their size.
                            Instances For
                              def GapCVP.CNFEncodedClauseSort.DelimitedCompareTrace.secondPrefix (chosenStep : delimitedPairComparisonMachine.CfgOption delimitedPairComparisonMachine.Cfg) (lift : NonComparisonStepLift chosenStep) (outcome : EncodedWordOrdering) (count : ) (tail firstCounter firstReversed secondCounter secondReversed firstForward secondForward source sourcePrefix output : List Bool) :
                              StateTransition.EvalsToInTime chosenStep (delimitedCompareConfiguration 2 outcome (List.replicate count true ++ false :: tail) firstCounter firstReversed secondCounter secondReversed firstForward secondForward source sourcePrefix output) (some (delimitedCompareConfiguration 3 outcome tail firstCounter firstReversed (List.replicate count true ++ secondCounter) secondReversed firstForward secondForward (false :: (List.replicate count true ++ source)) (List.replicate (count + 1) true ++ sourcePrefix) output)) (count + 1)

                              Reads the second unary prefix using any compatible machine step.

                              Equations
                              • One or more equations did not get rendered due to their size.
                              Instances For
                                noncomputable def GapCVP.CNFEncodedClauseSort.delimitedCompareSecondPrefixTrace (outcome : EncodedWordOrdering) (count : ) (tail firstCounter firstReversed secondCounter secondReversed firstForward secondForward source sourcePrefix output : List Bool) :
                                StateTransition.EvalsToInTime delimitedPairComparisonMachine.step (delimitedCompareConfiguration 2 outcome (List.replicate count true ++ false :: tail) firstCounter firstReversed secondCounter secondReversed firstForward secondForward source sourcePrefix output) (some (delimitedCompareConfiguration 3 outcome tail firstCounter firstReversed (List.replicate count true ++ secondCounter) secondReversed firstForward secondForward (false :: (List.replicate count true ++ source)) (List.replicate (count + 1) true ++ sourcePrefix) output)) (count + 1)

                                Internal support shared across GapCVP continuation modules.

                                Equations
                                • One or more equations did not get rendered due to their size.
                                Instances For
                                  def GapCVP.CNFEncodedClauseSort.DelimitedCompareTrace.secondMissingPrefix (chosenStep : delimitedPairComparisonMachine.CfgOption delimitedPairComparisonMachine.Cfg) (lift : NonComparisonStepLift chosenStep) (outcome : EncodedWordOrdering) (count : ) (firstCounter firstReversed secondCounter secondReversed firstForward secondForward source sourcePrefix output : List Bool) :
                                  StateTransition.EvalsToInTime chosenStep (delimitedCompareConfiguration 2 outcome (List.replicate count true) firstCounter firstReversed secondCounter secondReversed firstForward secondForward source sourcePrefix output) (some (delimitedCompareConfiguration 7 EncodedWordOrdering.invalid [] firstCounter firstReversed (List.replicate count true ++ secondCounter) secondReversed firstForward secondForward (List.replicate count true ++ source) (List.replicate count true ++ sourcePrefix) output)) (count + 1)

                                  Detects a missing second delimiter using any compatible machine step.

                                  Equations
                                  • One or more equations did not get rendered due to their size.
                                  Instances For
                                    noncomputable def GapCVP.CNFEncodedClauseSort.delimitedCompareSecondMissingPrefixTrace (outcome : EncodedWordOrdering) (count : ) (firstCounter firstReversed secondCounter secondReversed firstForward secondForward source sourcePrefix output : List Bool) :
                                    StateTransition.EvalsToInTime delimitedPairComparisonMachine.step (delimitedCompareConfiguration 2 outcome (List.replicate count true) firstCounter firstReversed secondCounter secondReversed firstForward secondForward source sourcePrefix output) (some (delimitedCompareConfiguration 7 EncodedWordOrdering.invalid [] firstCounter firstReversed (List.replicate count true ++ secondCounter) secondReversed firstForward secondForward (List.replicate count true ++ source) (List.replicate count true ++ sourcePrefix) output)) (count + 1)

                                    Internal support shared across GapCVP continuation modules.

                                    Equations
                                    • One or more equations did not get rendered due to their size.
                                    Instances For
                                      def GapCVP.CNFEncodedClauseSort.DelimitedCompareTrace.secondPartialPayload (chosenStep : delimitedPairComparisonMachine.CfgOption delimitedPairComparisonMachine.Cfg) (lift : NonComparisonStepLift chosenStep) (outcome : EncodedWordOrdering) (payload remainingCounter firstCounter firstReversed secondReversed firstForward secondForward source sourcePrefix output : List Bool) :
                                      StateTransition.EvalsToInTime chosenStep (delimitedCompareConfiguration 3 outcome payload firstCounter firstReversed (List.replicate payload.length true ++ remainingCounter) secondReversed firstForward secondForward source sourcePrefix output) (some (delimitedCompareConfiguration 3 outcome [] firstCounter firstReversed remainingCounter (payload.reverse ++ secondReversed) firstForward secondForward (payload.reverse ++ source) (List.replicate payload.length true ++ sourcePrefix) output)) payload.length

                                      Reads an incomplete second payload using any compatible machine step.

                                      Equations
                                      • One or more equations did not get rendered due to their size.
                                      Instances For
                                        noncomputable def GapCVP.CNFEncodedClauseSort.delimitedCompareSecondPartialPayloadTrace (outcome : EncodedWordOrdering) (payload remainingCounter firstCounter firstReversed secondReversed firstForward secondForward source sourcePrefix output : List Bool) :
                                        StateTransition.EvalsToInTime delimitedPairComparisonMachine.step (delimitedCompareConfiguration 3 outcome payload firstCounter firstReversed (List.replicate payload.length true ++ remainingCounter) secondReversed firstForward secondForward source sourcePrefix output) (some (delimitedCompareConfiguration 3 outcome [] firstCounter firstReversed remainingCounter (payload.reverse ++ secondReversed) firstForward secondForward (payload.reverse ++ source) (List.replicate payload.length true ++ sourcePrefix) output)) payload.length

                                        Internal support shared across GapCVP continuation modules.

                                        Equations
                                        • One or more equations did not get rendered due to their size.
                                        Instances For
                                          def GapCVP.CNFEncodedClauseSort.DelimitedCompareTrace.firstRecord (chosenStep : delimitedPairComparisonMachine.CfgOption delimitedPairComparisonMachine.Cfg) (lift : NonComparisonStepLift chosenStep) (outcome : EncodedWordOrdering) (payload tail firstReversed secondCounter secondReversed firstForward secondForward source sourcePrefix output : List Bool) :
                                          StateTransition.EvalsToInTime chosenStep (delimitedCompareConfiguration 0 outcome (BinaryEncoding.lengthPrefixedWord payload ++ tail) [] firstReversed secondCounter secondReversed firstForward secondForward source sourcePrefix output) (some (delimitedCompareConfiguration 2 outcome tail [] (payload.reverse ++ firstReversed) secondCounter secondReversed firstForward secondForward ((BinaryEncoding.lengthPrefixedWord payload).reverse ++ source) (List.replicate (BinaryEncoding.lengthPrefixedWord payload).length true ++ sourcePrefix) output)) (2 * payload.length + 2)

                                          Reads the first length-prefixed record using any compatible machine step.

                                          Equations
                                          • One or more equations did not get rendered due to their size.
                                          Instances For
                                            noncomputable def GapCVP.CNFEncodedClauseSort.delimitedCompareFirstRecordTrace (outcome : EncodedWordOrdering) (payload tail firstReversed secondCounter secondReversed firstForward secondForward source sourcePrefix output : List Bool) :
                                            StateTransition.EvalsToInTime delimitedPairComparisonMachine.step (delimitedCompareConfiguration 0 outcome (BinaryEncoding.lengthPrefixedWord payload ++ tail) [] firstReversed secondCounter secondReversed firstForward secondForward source sourcePrefix output) (some (delimitedCompareConfiguration 2 outcome tail [] (payload.reverse ++ firstReversed) secondCounter secondReversed firstForward secondForward ((BinaryEncoding.lengthPrefixedWord payload).reverse ++ source) (List.replicate (BinaryEncoding.lengthPrefixedWord payload).length true ++ sourcePrefix) output)) (2 * payload.length + 2)

                                            Internal support shared across GapCVP continuation modules.

                                            Equations
                                            • One or more equations did not get rendered due to their size.
                                            Instances For
                                              def GapCVP.CNFEncodedClauseSort.DelimitedCompareTrace.secondRecord (chosenStep : delimitedPairComparisonMachine.CfgOption delimitedPairComparisonMachine.Cfg) (lift : NonComparisonStepLift chosenStep) (outcome : EncodedWordOrdering) (payload tail firstCounter firstReversed secondReversed firstForward secondForward source sourcePrefix output : List Bool) :
                                              StateTransition.EvalsToInTime chosenStep (delimitedCompareConfiguration 2 outcome (BinaryEncoding.lengthPrefixedWord payload ++ tail) firstCounter firstReversed [] secondReversed firstForward secondForward source sourcePrefix output) (some (delimitedCompareConfiguration 4 outcome tail firstCounter firstReversed [] (payload.reverse ++ secondReversed) firstForward secondForward ((BinaryEncoding.lengthPrefixedWord payload).reverse ++ source) (List.replicate (BinaryEncoding.lengthPrefixedWord payload).length true ++ sourcePrefix) output)) (2 * payload.length + 2)

                                              Reads the second length-prefixed record using any compatible machine step.

                                              Equations
                                              • One or more equations did not get rendered due to their size.
                                              Instances For
                                                noncomputable def GapCVP.CNFEncodedClauseSort.DelimitedCompareTrace.validAssembly (chosenStep : delimitedPairComparisonMachine.CfgOption delimitedPairComparisonMachine.Cfg) (lift : NonComparisonStepLift chosenStep) (first second suffix firstResidual secondResidual : List Bool) (comparisonOutcome : EncodedWordOrdering) (comparisonTime : ) (comparisonTrace : StateTransition.EvalsToInTime chosenStep (delimitedCompareConfiguration 6 EncodedWordOrdering.invalid suffix [] [] [] [] first second ((BinaryEncoding.lengthPrefixedWord second).reverse ++ (BinaryEncoding.lengthPrefixedWord first).reverse) (List.replicate (BinaryEncoding.lengthPrefixedWord second).length true ++ List.replicate (BinaryEncoding.lengthPrefixedWord first).length true) []) (some (delimitedCompareConfiguration 7 comparisonOutcome suffix [] [] [] [] firstResidual secondResidual ((BinaryEncoding.lengthPrefixedWord second).reverse ++ (BinaryEncoding.lengthPrefixedWord first).reverse) (List.replicate (BinaryEncoding.lengthPrefixedWord second).length true ++ List.replicate (BinaryEncoding.lengthPrefixedWord first).length true) [])) comparisonTime) :

                                                Parses both records, runs a supplied phase-six comparison, and restores the input.

                                                Equations
                                                • One or more equations did not get rendered due to their size.
                                                Instances For
                                                  @[simp]

                                                  Internal support shared across GapCVP continuation modules.

                                                  Internal support shared across GapCVP continuation modules.

                                                  Internal support shared across GapCVP continuation modules.