Language oracles, transducers and zero-error randomized oracle machines
DefinitionNCFactorClosure607_Circuits_Supplement_MachinesOracle transducers. A deterministic oracle transducer is a published Cook–Levin oracle machine: a multi-tape Turing machine with a query state, an answer state, a query tape and an answer tape, which makes one oracle call per step. The oracle of a language answers by if and by otherwise. With oracle , on input , the machine outputs within steps means that after steps it is in its halting state with on its output tape. and are the published classes of languages over given by one existential, or one existential and one universal, polynomially bounded quantifier over a polynomial-time checking relation.
Randomized oracle machines. A randomized oracle machine is such an oracle machine with one more work tape that initially holds an infinite sequence of coins. The coins are independent and fair: is distributed by the infinite product of uniform measures on . The running time on input and coins is the first step at which the machine is in its halting state, or if it never halts; its output is then the content of its output tape.
These are the machine models of Theorems 8.1 and 8.2.
Formalization Note In the first steps a query is read with cells of fuel, which covers every query the machine can write in steps, as in the published oracle-machine model.
A polynomially clocked deterministic oracle transducer halts within steps on every bit string and for every membership oracle. The input promise restricts correctness only.
import Mathlib
import Definitions.Def_ConsModCount_Complexity
import Definitions.Def_BudgetCoreExchange_Sigma2P
import Definitions.Def_NCFactorClosure607_Circuits_Supplement_Encoding
/-!
# Oracle machines with a language oracle, and randomized oracle machines
Arvind–Joglekar, *Factor Closure in Noncommutative Algebraic Complexity*,
STOC 2027 submission #607, §8, p.18–21 (the classes `FP^{Σ₂^P}` and zero-error randomized
computation with an `NP` oracle).
* Deterministic oracle transducers are the published oracle machines
`ConsModCount.OracleMachine` (multi-tape Cook–Levin machines with a query tape, an answer tape
and one-step oracle calls). The oracle of a language `O ⊆ {0,1}*` answers a query `q` with the
one-bit string `1` if `q ∈ O` and `0` otherwise.
* The classes `NP` and `Σ₂^P` of languages over `{0,1}` are the published `CookPvsNP.NP Bool`
and `BudgetCoreExchange.Sigma2P Bool` (∃ and ∃∀ over a polynomial-time checking relation).
* A **randomized oracle machine** is an oracle machine with an additional work tape that holds an
infinite sequence `ω` of fair coins (cell `0` holds the start symbol, cell `i + 1` the coin
`ω i`). Its coins are distributed by the product of fair Bernoulli measures on `ℕ → Bool`. Its
running time on input `x` and coins `ω` is the first step at which it is in its halting state
(`⊤` if it never halts); queries made in the first `t` steps are read with `t + 2` cells of
fuel, which covers every query written in `t` steps.
-/
namespace NCFactorClosure607.Circuits.Supplement
open MeasureTheory
open scoped Classical in
/-- The oracle of a language `O`: the query `q` is answered by `1` if `q ∈ O`, by `0`
otherwise. -/
noncomputable def langOracle (O : Set (List Bool)) : List Bool → List Bool :=
fun q => if q ∈ O then [true] else [false]
/-- The oracle machine `Mo`, with oracle answers `ans`, started on input `x`, is in its halting
state after `T` steps and its output tape then holds `y` (queries read with `T + 2` cells of
fuel, as in `ConsModCount.OracleMachine.ComputesInTime`). -/
def OracleOutputsIn (Mo : ConsModCount.OracleMachine) (ans : List Bool → List Bool)
(x : List Bool) (T : ℕ) (y : List Bool) : Prop :=
(Mo.run ans (T + 2) (CookLevin.startConfig2 Mo.k (CookLevin.boolsToSymbols x) []) T).1 =
Mo.M.length ∧
CookLevin.outputOf Mo.k
(Mo.run ans (T + 2) (CookLevin.startConfig2 Mo.k (CookLevin.boolsToSymbols x) []) T)
(T + 2) = y
/-- A polynomial clock on all inputs and for every membership oracle. The factorization
promise constrains correctness, not the transducer's polynomial running time. -/
def OraclePolyTime (Mo : ConsModCount.OracleMachine) (c e : ℕ) : Prop :=
∀ (L : Set (List Bool)) (x : List Bool),
(Mo.run (langOracle L) (CookLevin.polyBound c e x.length + 2)
(CookLevin.startConfig2 Mo.k (CookLevin.boolsToSymbols x) [])
(CookLevin.polyBound c e x.length)).1 = Mo.M.length
/-- A randomized oracle machine: an oracle machine with a designated coin tape. -/
structure RandOracleMachine extends ConsModCount.OracleMachine where
coinTape : ℕ
namespace RandOracleMachine
/-- Well-formedness: the oracle machine is well formed and the coin tape is a work tape distinct
from the input, output, query and answer tapes. -/
def WF (R : RandOracleMachine) : Prop :=
R.toOracleMachine.WF ∧ 1 ≤ R.coinTape ∧ R.coinTape < R.k - 1 ∧ R.coinTape ≠ R.qTape ∧
R.coinTape ≠ R.aTape
/-- The coin tape holding the coin sequence `ω`. -/
def coinTapeOf (ω : ℕ → Bool) : CookLevin.Tape :=
(fun i => if i = 0 then CookLevin.startSymbol else CookLevin.boolSym (ω (i - 1)), 0)
/-- The start configuration on input `x` with coins `ω`. -/
def startCfg (R : RandOracleMachine) (x : List Bool) (ω : ℕ → Bool) : CookLevin.Config :=
let c := CookLevin.startConfig2 R.k (CookLevin.boolsToSymbols x) []
(c.1, c.2.set R.coinTape (coinTapeOf ω))
/-- The configuration after `t` steps (queries read with `t + 2` cells of fuel). -/
def cfgAt (R : RandOracleMachine) (ans : List Bool → List Bool) (x : List Bool)
(ω : ℕ → Bool) (t : ℕ) : CookLevin.Config :=
R.run ans (t + 2) (R.startCfg x ω) t
/-- The machine is in its halting state after `t` steps. -/
def HaltedAt (R : RandOracleMachine) (ans : List Bool → List Bool) (x : List Bool)
(ω : ℕ → Bool) (t : ℕ) : Prop :=
(R.cfgAt ans x ω t).1 = R.M.length
open scoped Classical in
/-- The running time: the first step at which the machine is halted, `⊤` if it never halts. -/
noncomputable def runTime (R : RandOracleMachine) (ans : List Bool → List Bool) (x : List Bool)
(ω : ℕ → Bool) : ℕ∞ :=
if h : ∃ t, R.HaltedAt ans x ω t then (Nat.find h : ℕ∞) else ⊤
/-- The output at the halting time (meaningful when the machine halts). -/
noncomputable def outputAt (R : RandOracleMachine) (ans : List Bool → List Bool)
(x : List Bool) (ω : ℕ → Bool) (t : ℕ) : List Bool :=
CookLevin.outputOf R.k (R.cfgAt ans x ω t) (t + 2)
end RandOracleMachine
/-- The distribution of the coins: independent fair coins, the product of uniform measures on
`Bool`. -/
noncomputable def coinMeasure : Measure (ℕ → Bool) :=
Measure.infinitePi fun _ : ℕ => (PMF.uniformOfFintype Bool).toMeasure
end NCFactorClosure607.Circuits.Supplement