Questions tagged [oracles]

In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to solve certain decision problems in a single operation.

Filter by
Sorted by
Tagged with
0
votes
1answer
23 views

Let $A,B,C$ be a complexity classes, are $A \subseteq B \Longrightarrow A^C \subseteq B^C$?

Let $A,B,C$ be a compleixty classes is $A \subseteq B \Longrightarrow A^C \subseteq B^C$. So $A \subseteq B$ given oracle access to some $L \in C$ complete, follow that $A^C \subseteq B^C$. is that ...
2
votes
1answer
56 views

Extensions of the Turing jump

The Turing jump $0^{(\alpha)}$ is defined for ordinals $\alpha<\omega_1^{\mathit{CK}}$ with $0^{(0)} = \varnothing$, $0^{(\alpha+1)}$ is the diagonal halting problem using $0^{(\alpha)}$ as an ...
0
votes
0answers
46 views

Decidability of convergence of real series given an oracle for positive series

I've been reading for the last hour a few posts on this site about series that no one knows if they converge or not. I was quite surprised that they were almost all consisting of positive terms. ...
1
vote
1answer
23 views

Modula computation with a oracle

Assume we have unknown number $d$ and an oracle which can tell us in one step if for any residual $x$ the equation $(1)$ $d \equiv x \textrm{ mod } p$ , with $p$ prime, holds. The important thing here ...
0
votes
1answer
62 views

Is a TM with oracle also a TM?

From Ullman's Introduction to Automata Theory, Languages and Computation, in a TM with oracle $A$ : Observe that if $A$ is a recursive set, then the oracle $A$ can be simulated by another Turing ...
0
votes
0answers
25 views

Is a halting problem oracle to itself possible if randomness exist?

The usual proof that a halting problem oracle to itself don't exist is like: Check if itself halt, and do the opposite. Both result are conflict. However, if it sometimes return HALT while ...
1
vote
1answer
89 views

What did Nemirovski and Yudin actually do in their 1978 article problem complexity and method efficiency in optimization?

What did Nemirovski and Yudin actually do in their 1978 book problem complexity and method efficiency in optimization? I'm struggling to find very much on it.
2
votes
1answer
223 views

Question about Friedberg’s original proof of the Friedberg-Muchnik Theorem

This is Richard Friedberg’s original 1957 proof of the Friedberg-Muchnik Theorem, the origin of the ground-breaking priority argument. It is actually surprisingly understandable once you get past the ...
3
votes
1answer
127 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
60 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
84 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
88 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
138 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
67 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
134 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
94 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 ...
3
votes
2answers
235 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
94 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
157 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
125 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
151 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
94 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
293 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
204 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
105 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
134 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 ...