We’re rewarding the question askers & reputations are being recalculated! Read more.

Questions tagged [oracles]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
3
votes
1answer
84 views

What ordinals are computable using $\Sigma^1_2$ and $\Pi^1_2$ truth?

The least non-recursive ordinal is $\omega_1^{CK}$, the Church-Kleene ordinal. But with the benefit of oracles, you can compute more ordinals. Or at least you can with the benefit of sufficiently ...
0
votes
1answer
36 views

What is the smallest ordinal not computable by using artihmetical truth as an oracle?

Kleene's $O$ is a way to use natural numbers as notations for recursive ordinals. I’m wondering what happens if you modify the definition of Kleene’s $O$ to allow for arithmetical truth as an oracle. ...
0
votes
1answer
52 views

Is there a simple oracle that computes the ordinal $\beta_0$?

There is a certain large countable ordinal referred to in the literature as $\beta_0$. It was first discovered by Paul Cohen, and here are some equivalent characterizations of it: The smallest ...
1
vote
1answer
39 views

What is the highest ordinal that can’t be obtained from Kleene’s O with oracles?

Kleene’s $O$ is a way to use natural numbers as notations for recursive ordinals. $0$ is a notation for $0$. If $i$ is a notation for $\alpha$, then $2^i$ is a notation for $\alpha+1$. And if $\...
5
votes
1answer
93 views

How does the frequentist definition of probability work with non-measurable sets?

Let $E$ be a subset of $[0,1]$, and let us try to create a measure of $E$ as follows. Let $x_1,x_2,...$ be a sequence of independent random real numbers picked using a uniform probability ...
0
votes
1answer
39 views

How strong is an oracle that avoid don't-halt

Consider such an oracle: Given a turing machine[1], return the halting state it falls on, or arbitary result(but don't stuck in) if the TM doesn't halt. How strong is a TM with the oracle? Can the ...
2
votes
1answer
83 views

Where is the theorem related to the construction of countable admissible ordinals by Turing machines with oracles?

Wikipedia contains the following information in the article "Admissible ordinal": By a theorem of Sacks, the countable admissible ordinals are exactly those constructed in a manner similar to the ...
1
vote
2answers
90 views

How exactly does the oracle for a well-order of order type $\omega_1^\text{CK}$ operate?

The concept of an oracle for Turing machines assumes that the oracle answers Yes/No to a particular question $Q$, assuming that $Q$ is formulated as a bitstring on the oracle tape (instead of ...
2
votes
2answers
162 views

Is it possible to construct a model of oracle Turing machines that correspond to $\omega_n^\text{CK}$, where $n$ is greater than $1$?

I have found the following quotes. Quote $1$ ( source ): In computability theory, Turing Machines+BB oracles correspond to the same ordinal as ordinary Turing Machines ($\omega_1^\text{CK}$). In ...
0
votes
2answers
60 views

not a computable function

Define $\Phi_e^K(x)$ to be the output of the eth Turing machine that has K (the diagonal language) on its oracle tape and x on its input tape. Is the map f: (x,e) $\mapsto$ $\Phi^K_e(x)$ a computable ...
3
votes
1answer
122 views

Church's thesis for oracle computations

Church's thesis states that any reasonable definition of computability (over subsets or functions of $\mathbb{N}$) coincide. My question is, is there an analogous result/thesis for oracle computations?...
3
votes
1answer
122 views

Any non-standard halting oracles stronger than $\mathbb N$?

Let $M$ be some model of PA. Let $H_M$ be the set of codes of standard turing machines $X$ such that $M \models X \text{ halts}$. For example, $H_\mathbb N$ corresponds to the regular halting oracle (...
0
votes
1answer
120 views

Finite Medvedev degree

I'm moving my first steps in the world of Medvedev degrees and I have a simple question: how can a Medvedev degree be finite (and different from $\mathbf{1}$)? For sake of completeness let me state ...
1
vote
1answer
91 views

Understanding the complexity class $P^O$ for randomized oracles

We know from Toda's theorem that $PH \subseteq P^{PP}$. What do we know about the following classes? $$ P^{ZPP}, P^{RP}, \text{ and } P^{BPP} $$
1
vote
1answer
216 views

Oracle Turing machine - $E_{\text{TM}}$ and $PCP$.

$$E_{\text{TM}}=\{\langle M\rangle|M\text{ is a TM and $L(M)=\emptyset$}\}.$$ $E_{\text{TM}}$ is undecidable $$PCP=\{\langle P\rangle|P\text{ is an instance of the Post Correspondence Problem with a ...
0
votes
1answer
43 views

Impact on probability distribution when introducing new information

Consider a context in which $f(X)$ is a probability density function for a given random variable $X$, with domain comprised in $[l,u]$ ($l$ = lower bound, $u$ = upper bound). Now, consider that ...
4
votes
1answer
184 views

How many digits of Chaitin's $\Omega$ constant would we know if we had a $\Sigma_1$-Oracle?

According to Wikipedia (and it seems intuitive from the definition itself), $\Omega$ is Turing equivalent to the halting problem and thus at level $\Delta_2^0$ of the arithmetical hierarchy. Do this ...
2
votes
1answer
102 views

Searching for a secret, given a non-uniform distribution

Let $s$ be an unknown bit string of length $n$. Let $p(i, b)$ be the probability that $i$-th bit of $s$ is equal to $b \in \{0,1\}$. What's the fastest method to find $s$, given the distribution $p()$?...
5
votes
2answers
129 views

Can we implement $\omega^{CK}_1$ using $\omega^{CK}_1+1$ as an oracle?

Let $\omega^{CK}_1$ denote the least non-recursive ordinal. Suppose we have an unknown well-ordering of $\mathbb{N}$ of the order type $\omega^{CK}_1+1$ as an oracle. Is it possible to write an ...