Ternary machine-acceptance vote data
Definitionsgl_ternary_machine_vote_dataThis module defines the machine-acceptance version of the ternary amplification vote. For each leaf random block it forms the two-tape verifier input and records whether the supplied base machine accepts at its prescribed clock; those leaf bits are then folded by the same complete ternary-majority tree used by the mission construction. The module also proves a congruence lemma for ternary votes and shows that, under the base machine correctness hypothesis, the machine-acceptance vote equals the original verifier vote.
Definition code
import Definitions.Def_sgl_verifier_constructions
namespace SipserGacsLautemann
def ternaryTwoTapeInput
(input : Fin 2 → List Bool) (random : List Bool) :
Fin 2 → List Bool :=
fun i => if i = 0 then input 0 else random
@[simp]
theorem ternaryTwoTapeInput_zero
(input : Fin 2 → List Bool) (random : List Bool) :
ternaryTwoTapeInput input random 0 = input 0 := by
simp [ternaryTwoTapeInput]
@[simp]
theorem ternaryTwoTapeInput_one
(input : Fin 2 → List Bool) (random : List Bool) :
ternaryTwoTapeInput input random 1 = random := by
simp [ternaryTwoTapeInput]
noncomputable def ternaryBaseMachineLeafVote
{states : Nat}
(machine : Machine 2 states)
(time : Nat → Nat)
(input : Fin 2 → List Bool)
(random : List Bool) : Bool :=
@decide
(machine.acceptsWithin
(ternaryTwoTapeInput input random)
(time
(totalInputLength
(ternaryTwoTapeInput input random))))
(Classical.propDecidable _)
noncomputable def ternaryBaseMachineVote
{states : Nat}
(machine : Machine 2 states)
(time : Nat → Nat)
(depth : Nat → Nat)
(input : Fin 2 → List Bool) : Bool :=
let d := depth (input 0).length
let leafCount := 3 ^ d
let randomBits := (input 1).length / leafCount
ternaryVoteConstruction
(ternaryBaseMachineLeafVote machine time input)
d
(ternaryListTreeConstruction randomBits d (input 1))
theorem ternaryVoteConstruction_congr
{Ω : Type*}
(vote₁ vote₂ : Ω → Bool)
(hagrees : ∀ sample, vote₁ sample = vote₂ sample) :
∀ (depth : Nat)
(sample : TernarySampleConstruction Ω depth),
ternaryVoteConstruction vote₁ depth sample =
ternaryVoteConstruction vote₂ depth sample
| 0, sample => hagrees sample
| depth + 1, sample => by
simp only [ternaryVoteConstruction]
rw [ternaryVoteConstruction_congr vote₁ vote₂
hagrees depth sample.1,
ternaryVoteConstruction_congr vote₁ vote₂
hagrees depth sample.2.1,
ternaryVoteConstruction_congr vote₁ vote₂
hagrees depth sample.2.2]
theorem ternaryBaseMachineLeafVote_eq_verifier
(verifier : List Bool → List Bool → Bool)
{states : Nat}
(machine : Machine 2 states)
(time : Nat → Nat)
(hcorrect :
∀ input : Fin 2 → List Bool,
(machine.acceptsWithin input
(time (totalInputLength input)) ↔
verifier (input 0) (input 1) = true) ∧
(machine.rejectsWithin input
(time (totalInputLength input)) ↔
¬ verifier (input 0) (input 1) = true))
(input : Fin 2 → List Bool)
(random : List Bool) :
ternaryBaseMachineLeafVote machine time input random =
verifier (input 0) random := by
classical
let query := ternaryTwoTapeInput input random
have hacceptIff :
machine.acceptsWithin query
(time (totalInputLength query)) ↔
verifier (input 0) random = true := by
simpa [query] using (hcorrect query).1
by_cases haccept :
machine.acceptsWithin query
(time (totalInputLength query))
· have hverifier : verifier (input 0) random = true :=
hacceptIff.mp haccept
simp [ternaryBaseMachineLeafVote, query, haccept,
hverifier]
· have hverifier : verifier (input 0) random = false := by
cases hvalue : verifier (input 0) random with
| false => rfl
| true =>
exact False.elim
(haccept (hacceptIff.mpr (by simpa using hvalue)))
simp [ternaryBaseMachineLeafVote, query, haccept,
hverifier]
theorem ternaryBaseMachineVote_eq_verifierVote
(verifier : List Bool → List Bool → Bool)
{states : Nat}
(machine : Machine 2 states)
(time : Nat → Nat)
(depth : Nat → Nat)
(hcorrect :
∀ input : Fin 2 → List Bool,
(machine.acceptsWithin input
(time (totalInputLength input)) ↔
verifier (input 0) (input 1) = true) ∧
(machine.rejectsWithin input
(time (totalInputLength input)) ↔
¬ verifier (input 0) (input 1) = true))
(input : Fin 2 → List Bool) :
ternaryBaseMachineVote machine time depth input =
(let d := depth (input 0).length
let leafCount := 3 ^ d
let randomBits := (input 1).length / leafCount
ternaryVoteConstruction (verifier (input 0)) d
(ternaryListTreeConstruction randomBits d (input 1))) := by
unfold ternaryBaseMachineVote
exact
ternaryVoteConstruction_congr
(ternaryBaseMachineLeafVote machine time input)
(verifier (input 0))
(ternaryBaseMachineLeafVote_eq_verifier
verifier machine time hcorrect input)
(depth (input 0).length)
(ternaryListTreeConstruction
((input 1).length / 3 ^ depth (input 0).length)
(depth (input 0).length) (input 1))
end SipserGacsLautemann
Source
Prove2me Sipser--Gács--Lautemann mission ternary-majority scheduler construction.