Bounded unary-offset virtual input data
Definitionsgl_bounded_unary_offset_dataThis module defines the virtual four-tape input used by the bounded-unary scheduler. Given a three-tape input and a natural offset , it forms the four-tape input . It proves the exact total-length formula and the bound needed when : the virtual four-tape input has total length at most twice the original three-tape input length. It also defines a classical Boolean decision helper for whether the supplied base machine accepts at some bounded unary offset.
Definition code
import Definitions.Def_sipser_gacs_lautemann
import Mathlib.Algebra.BigOperators.Fin
import Mathlib.Tactic.FinCases
namespace SipserGacsLautemann
def boundedUnaryOffsetInput
(input : Fin 3 → List Bool) (offset : Nat) :
Fin 4 → List Bool :=
fun j =>
if j = 0 then input 0
else if j = 1 then input 1
else if j = 2 then input 2
else List.replicate offset true
@[simp]
theorem boundedUnaryOffsetInput_zero
(input : Fin 3 → List Bool) (offset : Nat) :
boundedUnaryOffsetInput input offset 0 = input 0 := by
simp [boundedUnaryOffsetInput]
@[simp]
theorem boundedUnaryOffsetInput_one
(input : Fin 3 → List Bool) (offset : Nat) :
boundedUnaryOffsetInput input offset 1 = input 1 := by
simp [boundedUnaryOffsetInput]
@[simp]
theorem boundedUnaryOffsetInput_two
(input : Fin 3 → List Bool) (offset : Nat) :
boundedUnaryOffsetInput input offset 2 = input 2 := by
simp [boundedUnaryOffsetInput]
@[simp]
theorem boundedUnaryOffsetInput_three
(input : Fin 3 → List Bool) (offset : Nat) :
boundedUnaryOffsetInput input offset 3 =
List.replicate offset true := by
simp [boundedUnaryOffsetInput]
theorem boundedUnaryOffsetInput_eq_original
(input : Fin 3 → List Bool) (offset : Nat) :
boundedUnaryOffsetInput input offset =
fun j : Fin 4 =>
if j = 0 then input 0
else if j = 1 then input 1
else if j = 2 then input 2
else List.replicate offset true := by
rfl
theorem totalInputLength_boundedUnaryOffsetInput
(input : Fin 3 → List Bool) (offset : Nat) :
totalInputLength (boundedUnaryOffsetInput input offset) =
totalInputLength input + offset := by
simp only [totalInputLength, List.sum_ofFn]
rw [Fin.sum_univ_four, Fin.sum_univ_three]
simp [boundedUnaryOffsetInput]
theorem totalInputLength_boundedUnaryOffsetInput_le
(input : Fin 3 → List Bool)
(offset : Fin ((input 2).length + 1)) :
totalInputLength
(boundedUnaryOffsetInput input offset.val) ≤
2 * totalInputLength input := by
rw [totalInputLength_boundedUnaryOffsetInput]
have hoffset : offset.val ≤ (input 2).length :=
Nat.lt_succ_iff.mp offset.isLt
have hcomponent :
(input 2).length ≤ totalInputLength input := by
simp only [totalInputLength, List.sum_ofFn]
rw [Fin.sum_univ_three]
omega
omega
def boundedUnaryOffsetBaseAccepts
{states : Nat}
(machine : Machine 4 states)
(time : Nat → Nat)
(input : Fin 3 → List Bool) : Prop :=
∃ offset : Fin ((input 2).length + 1),
machine.acceptsWithin
(boundedUnaryOffsetInput input offset.val)
(time
(totalInputLength
(boundedUnaryOffsetInput input offset.val)))
noncomputable def boundedUnaryOffsetBaseAcceptDecision
{states : Nat}
(machine : Machine 4 states)
(time : Nat → Nat)
(input : Fin 3 → List Bool) : Bool :=
@decide
(boundedUnaryOffsetBaseAccepts machine time input)
(Classical.propDecidable _)
end SipserGacsLautemann
Source
Prove2me Sipser--Gács--Lautemann mission bounded-unary scheduler construction.