Documentation

LeanPool.GapCVP.Part03C

GapCVP proof, part 03, continuation 03 #

GapCVP reduction support.

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

      GapCVP reduction support.

      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

          Internal support shared across GapCVP continuation modules.

          Equations
          Instances For

            GapCVP reduction support.

            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

                Internal support shared across GapCVP continuation modules.

                Equations
                Instances For

                  Internal support shared across GapCVP continuation modules.

                  theorem GapCVP.FormulaTuringTM.binaryStackDecrement_value (bits remaining : List Bool) (hdecrement : binaryStackDecrement bits = some remaining) :

                  Internal support shared across GapCVP continuation modules.

                  Internal support shared across GapCVP continuation modules.

                  GapCVP reduction support.

                  Equations
                  Instances For

                    Internal support shared across GapCVP continuation modules.

                    Equations
                    Instances For

                      Internal support shared across GapCVP continuation modules.

                      Equations
                      Instances For

                        GapCVP reduction support.

                        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

                            GapCVP reduction support.

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

                              GapCVP reduction support.

                              Equations
                              • One or more equations did not get rendered due to their size.
                              Instances For
                                def GapCVP.FormulaTuringTM.canonicalConfiguration (phase : Fin 17) (input counter field binary borrow output : List Bool) :

                                GapCVP reduction support.

                                Equations
                                Instances For
                                  theorem GapCVP.FormulaTuringTM.canonical_header_prefix_true (input counter field binary borrow output : List Bool) :
                                  canonicalFormulaMachine.step (canonicalConfiguration 0 (true :: input) counter field binary borrow output) = some (canonicalConfiguration 0 input (true :: counter) field binary borrow output)

                                  Internal support shared across GapCVP continuation modules.

                                  theorem GapCVP.FormulaTuringTM.canonical_header_prefix_missing (counter field binary borrow output : List Bool) :
                                  canonicalFormulaMachine.step (canonicalConfiguration 0 [] counter field binary borrow output) = some (canonicalConfiguration 15 [] counter field binary borrow output)

                                  Internal support shared across GapCVP continuation modules.

                                  theorem GapCVP.FormulaTuringTM.canonical_header_payload_step (bit : Bool) (input counter field binary borrow output : List Bool) :
                                  canonicalFormulaMachine.step (canonicalConfiguration 1 (bit :: input) (true :: counter) field binary borrow output) = some (canonicalConfiguration 1 input counter (bit :: field) binary borrow output)

                                  Internal support shared across GapCVP continuation modules.

                                  theorem GapCVP.FormulaTuringTM.canonical_header_payload_missing (counter field binary borrow output : List Bool) :
                                  canonicalFormulaMachine.step (canonicalConfiguration 1 [] (true :: counter) field binary borrow output) = some (canonicalConfiguration 15 [] (true :: counter) field binary borrow output)

                                  Internal support shared across GapCVP continuation modules.

                                  theorem GapCVP.FormulaTuringTM.canonical_header_payload_complete (input field binary borrow output : List Bool) :
                                  canonicalFormulaMachine.step (canonicalConfiguration 1 input [] field binary borrow output) = some (canonicalConfiguration 2 input [] field binary borrow output)

                                  Internal support shared across GapCVP continuation modules.

                                  theorem GapCVP.FormulaTuringTM.canonical_header_check_true (input field binary borrow output : List Bool) :
                                  canonicalFormulaMachine.step (canonicalConfiguration 2 input [] (true :: field) binary borrow output) = some (canonicalConfiguration 3 input [] (true :: field) binary borrow output)

                                  Internal support shared across GapCVP continuation modules.

                                  theorem GapCVP.FormulaTuringTM.canonical_header_check_false (input field binary borrow output : List Bool) :
                                  canonicalFormulaMachine.step (canonicalConfiguration 2 input [] (false :: field) binary borrow output) = some (canonicalConfiguration 15 input [] (false :: field) binary borrow output)

                                  Internal support shared across GapCVP continuation modules.

                                  theorem GapCVP.FormulaTuringTM.canonical_header_check_zero (input binary borrow output : List Bool) :
                                  canonicalFormulaMachine.step (canonicalConfiguration 2 input [] [] binary borrow output) = some (canonicalConfiguration (canonicalPrefixLabel 0) input [] [] binary borrow output)

                                  Internal support shared across GapCVP continuation modules.

                                  theorem GapCVP.FormulaTuringTM.canonical_literal_prefix_true (position : Fin 3) (input counter field binary borrow output : List Bool) :
                                  canonicalFormulaMachine.step (canonicalConfiguration (canonicalPrefixLabel position) (true :: input) counter field binary borrow output) = some (canonicalConfiguration (canonicalPrefixLabel position) input (true :: counter) field binary borrow output)

                                  Internal support shared across GapCVP continuation modules.

                                  theorem GapCVP.FormulaTuringTM.canonical_literal_prefix_delimiter (position : Fin 3) (input counter field binary borrow output : List Bool) :
                                  canonicalFormulaMachine.step (canonicalConfiguration (canonicalPrefixLabel position) (false :: input) counter field binary borrow output) = some (canonicalConfiguration (canonicalPayloadLabel position) input counter field binary borrow output)

                                  Internal support shared across GapCVP continuation modules.

                                  theorem GapCVP.FormulaTuringTM.canonical_literal_payload_step (position : Fin 3) (bit : Bool) (input counter field binary borrow output : List Bool) :
                                  canonicalFormulaMachine.step (canonicalConfiguration (canonicalPayloadLabel position) (bit :: input) (true :: counter) field binary borrow output) = some (canonicalConfiguration (canonicalPayloadLabel position) input counter (bit :: field) binary borrow output)

                                  Internal support shared across GapCVP continuation modules.

                                  theorem GapCVP.FormulaTuringTM.canonical_literal_payload_missing (position : Fin 3) (counter field binary borrow output : List Bool) :
                                  canonicalFormulaMachine.step (canonicalConfiguration (canonicalPayloadLabel position) [] (true :: counter) field binary borrow output) = some (canonicalConfiguration 15 [] (true :: counter) field binary borrow output)

                                  Internal support shared across GapCVP continuation modules.

                                  theorem GapCVP.FormulaTuringTM.canonical_literal_field_true (position : Fin 3) (input field binary borrow output : List Bool) :
                                  canonicalFormulaMachine.step (canonicalConfiguration (canonicalPayloadLabel position) input [] (true :: field) binary borrow output) = some (canonicalConfiguration (canonicalClearLabel position) input [] (true :: field) binary borrow output)

                                  Internal support shared across GapCVP continuation modules.

                                  theorem GapCVP.FormulaTuringTM.canonical_literal_field_false (position : Fin 3) (input field binary borrow output : List Bool) :
                                  canonicalFormulaMachine.step (canonicalConfiguration (canonicalPayloadLabel position) input [] (false :: field) binary borrow output) = some (canonicalConfiguration 15 input [] (false :: field) binary borrow output)

                                  Internal support shared across GapCVP continuation modules.

                                  theorem GapCVP.FormulaTuringTM.canonical_literal_clear_step (position : Fin 3) (bit : Bool) (input field binary borrow output : List Bool) :
                                  canonicalFormulaMachine.step (canonicalConfiguration (canonicalClearLabel position) input [] (bit :: field) binary borrow output) = some (canonicalConfiguration (canonicalClearLabel position) input [] field binary borrow output)

                                  Internal support shared across GapCVP continuation modules.

                                  theorem GapCVP.FormulaTuringTM.canonical_zero_field_sign_step (position : Fin 3) (hposition : position 2) (sign : Bool) (input binary borrow output : List Bool) :

                                  Internal support shared across GapCVP continuation modules.

                                  theorem GapCVP.FormulaTuringTM.canonical_zero_field_completeClause (sign : Bool) (input binary borrow output : List Bool) :
                                  canonicalFormulaMachine.step (canonicalConfiguration (canonicalPayloadLabel 2) (sign :: input) [] [] binary borrow output) = some (canonicalConfiguration 13 input [] [] binary borrow output)

                                  Internal support shared across GapCVP continuation modules.

                                  Internal support shared across GapCVP continuation modules.

                                  Internal support shared across GapCVP continuation modules.

                                  def GapCVP.FormulaTuringTM.canonicalFailureTrace (input counter field binary borrow output : List Bool) :
                                  StateTransition.EvalsToInTime canonicalFormulaMachine.step (canonicalConfiguration 15 input counter field binary borrow output) (some (Turing.haltList canonicalFormulaMachine (false :: output))) (input.length + counter.length + field.length + binary.length + borrow.length + 1)

                                  Internal support shared across GapCVP continuation modules.

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

                                    Internal support shared across GapCVP continuation modules.

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

                                      Internal support shared across GapCVP continuation modules.

                                      Equations
                                      Instances For

                                        Internal support shared across GapCVP continuation modules.

                                        def GapCVP.FormulaCert.canonicalHeaderPrefixTrace (length : ) (tail counter field binary borrow output : List Bool) :

                                        Internal support shared across GapCVP continuation modules.

                                        Equations
                                        • One or more equations did not get rendered due to their size.
                                        Instances For
                                          def GapCVP.FormulaCert.canonicalHeaderCopyTrace (header suffix field binary borrow output : List Bool) :

                                          Internal support shared across GapCVP continuation modules.

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

                                            Internal support shared across GapCVP continuation modules.

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

                                              Internal support shared across GapCVP continuation modules.

                                              Instances For

                                                Internal support shared across GapCVP continuation modules.

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

                                                  Internal support shared across GapCVP continuation modules.

                                                  Internal support shared across GapCVP continuation modules.

                                                  def GapCVP.FormulaCert.canonicalBorrowFailureTrace (zeros : ) (input counter field borrow output : List Bool) :

                                                  Internal support shared across GapCVP continuation modules.

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

                                                    Internal support shared across GapCVP continuation modules.

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

                                                      Internal support shared across GapCVP continuation modules.

                                                      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

                                                          Internal support shared across GapCVP continuation modules.

                                                          theorem GapCVP.FormulaTotalCert.binaryStackDecrement_length (bits remaining : List Bool) (hdecrement : FormulaTuringTM.binaryStackDecrement bits = some remaining) :
                                                          remaining.length = bits.length

                                                          Internal support shared across GapCVP continuation modules.

                                                          Internal support shared across GapCVP continuation modules.

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

                                                            Internal support shared across GapCVP continuation modules.

                                                            Equations
                                                            • One or more equations did not get rendered due to their size.
                                                            Instances For
                                                              theorem GapCVP.FormulaTotalCert.canonical_literal_prefix_missing_counter (position : Fin 3) (counterBit : Bool) (counter field binary borrow output : List Bool) :
                                                              FormulaTuringTM.canonicalFormulaMachine.step (FormulaTuringTM.canonicalConfiguration (FormulaTuringTM.canonicalPrefixLabel position) [] (counterBit :: counter) field binary borrow output) = some (FormulaTuringTM.canonicalConfiguration 15 [] (counterBit :: counter) field binary borrow output)

                                                              Internal support shared across GapCVP continuation modules.

                                                              theorem GapCVP.FormulaTotalCert.canonical_literal_prefix_incomplete (position : Fin 3) (hposition : position 0) (field binary borrow output : List Bool) :

                                                              Internal support shared across GapCVP continuation modules.

                                                              Internal support shared across GapCVP continuation modules.

                                                              Internal support shared across GapCVP continuation modules.