Struct ComputableFunction 

pub struct ComputableFunction {
    pub name: &'static str,
    pub jump_level: Option<u32>,
    pub table: Vec<Option<u64>>,
}

A Turing machine oracle that answers membership queries for a set X ⊆ ℕ. Used to model oracle-relative computability in the RM hierarchy.

Fields

name: &'static str

A description / name for this function (e.g. “Halting problem oracle”).

jump_level: Option<u32>

Degree information: Some(k) means the function has degree 0^(k) (k-th jump).

table: Vec<Option<u64>>

The function table for inputs 0..table.len() (partial; None = diverges).

Implementations

impl ComputableFunction

pub fn indicator_below(bound: u64) -> Self

Create the characteristic function of the set {n | n < bound} (computable).

pub fn eval(&self, n: usize) -> Option<u64>

Evaluate at input n, returning None if the function diverges.

pub fn is_total_up_to(&self, n: usize) -> bool

Return true if this function is total on 0..n.

pub fn oracle_query(&self, input: usize, _steps: u32) -> Option<u64>

Simulate the n-th step of a Turing machine oracle computation (stub). In a full implementation this would run a UTM; here we return the table value.

Trait Implementations

impl Clone for ComputableFunction

fn clone(&self) -> ComputableFunction

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for ComputableFunction

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.