Questions tagged [computability-theory]

computable sets and functions, Turing degrees, c.e. degrees, models of computability, primitive recursion, oracle computation, models of computability, decision problems, undecidability, Turing jump, halting problem, notions of computable randomness, computable model theory, computable equivalence relation theory, arithmetic and hyperarithmetic hierarchy, infinitary computability, $\alpha$-recursion, complexity theory.

Filter by
Sorted by
Tagged with
0
votes
0answers
45 views

Maximal decidable Diophantine sets [closed]

Thanks to the negative solution of Hilbert's tenth problem by Matiyasevich, Robinson, Davis and Putnam we know that there can be no general algorithm for deciding if a given Diophantine equation has ...
2
votes
2answers
211 views

Is there any reasonable non-regular Gödel numbering of the language of arithmetic?

Let $\mathcal{L}$ be the language of arithmetic given as follows: $x::= {\sf v} \mid x'$ $t ::= x \mid 0 \mid {\sf S}t \mid (t+t) \mid (t\times t)$ $A ::= \bot \mid \top \mid t=t \mid \neg A \mid (A \...
9
votes
1answer
341 views

Does every cofinal branch through Kleene's O compute true arithmetic?

My question concerns cofinal branches through Kleene's $O$, which is a set of natural numbers and a computably enumerable relation $<_O$ on this set that provides ordinal denotations for any ...
2
votes
0answers
49 views

Constructing Turing degrees near $\mathcal{O}$

I'm looking for some examples of constructions for Turing degrees close to, but not above, Kleene's $\mathcal{O}$. I know of one by Jockusch and Simpson using forcing with hyperarithmetic, uniformly ...
3
votes
1answer
422 views

Turing machines with all runs decidable

$\DeclareMathOperator\Comp{\mathit{Comp}} \DeclareMathOperator\succ{\mathit{succ}}$Let $(\Phi_e)_{e\in\omega}$ be your favorite enumeration of Turing machines. For $e,n\in\omega$ there is a structure $...
8
votes
1answer
256 views

The lattice of analogues of Robinson's $Q$

This question was asked and bountied at MSE without response. Call a sentence $\varphi$ in the language of arithmetic $Q$-like iff $\mathbb{N}\models\varphi$ and $\{\varphi\}$ is essentially ...
3
votes
0answers
68 views

Post correspondence problem: Busy beaver variant

The Post correspondence problem (Wikipedia link) is to decide for $k$ pairs of strings $$(a_1,b_1), (a_2, b_2), ..., (a_k,b_k),$$ if there exists a finite sequence of numbers $c_j, 0\le j\le j_\max $ ...
0
votes
0answers
41 views

Reference about Relation between Probabilistic Turing Machine and Turing Machine of every hierarchy

What are the relation between Probabilistic Turing Machine and Turing Machine of every hierarchy, for instance, are the Probabilistic PDA and NPDA equivalent? the Probabilistic LBA and LBA equivalent?...
6
votes
1answer
174 views

Complexity of a combinatorial constraint

For two $k$-partitions $X,Y\in k^\omega$ of $\omega$ (seen as functions $\omega\rightarrow k$), we say $X,Y$ are almost disjoint iff $X^{-1}(i)\cap Y^{-1}(i)$ is finite for all $i<k$. Question: ...
2
votes
0answers
107 views

ITTMs with higher types

What is the complexity of Infinite Time Turing Machines (ITTMs) augmented with an initially empty set of real numbers, with the ability to add, remove, and test presence of a real number in the set? ...
3
votes
2answers
490 views

Provably undecidable number inequality?

Here is a question that popped into my head right as I fell asleep last night. I was thinking about constructions of irrational numbers, like pi. I was wondering if there are two constructions (any ...
8
votes
1answer
256 views

Transfinite algorithms

The Ford-Fulkerson algorithm is a classic algorithm that computes the maximum flow in a network. It is well-known that if irrational arc capacities are allowed, the algorithm does not necessarily ...
2
votes
1answer
142 views

What is the efficiency of this algorithm which decides the answer to the Boolean satisfiability problem? [closed]

I have just written a short javascript program which, given any boolean expression with $N$ variables, completes in N "ticks" of the clock and which makes the decision. I will explain this algorithm, ...
4
votes
1answer
120 views

Strengthening of Shoenfield's result on the recursive omega-rule

It is trivial to show that Peano artithmetic ($\mathsf{PA}$) supplemented with the $\omega$-rule is complete. Joseph Shoenfield (`On a Restricted $\omega$-Rule', Bull. Acad. Polon. Sci. 7 (1959): 405–...
2
votes
0answers
88 views

Is Steiner symmetrization “Turing complete”?

This question stems from intuition so it is a little soft. It concerns performing computation using transformations on sets. The idea is that a rearrangement like Steiner symmetrization might be "...
11
votes
0answers
423 views

Where did this presentation of Godel's theorem appear?

This question was asked and bountied at MSE, with no response. Many years ago I ran into the following proof of Godel's first incompleteness theorem (here $T$ is an "appropriate" theory of ...
2
votes
1answer
212 views

The fastest growing function of given complexity

Let $f$ be a computable function $\mathbb{N} \to \mathbb{N}$ be a computable function. Since a program of a computable function is a finite object we can define plain Kolmogorov complexity of $f$ (we ...
1
vote
1answer
81 views

Fixed points of recursive functions with finite range

Let $\phi$ be a programming system satisfying the UTM Theorem (i.e., $\phi$ is a $2$-ary partial recursive function such that the list $\phi_0,\phi_1,\ldots$ includes all $1$-ary partial recursive ...
1
vote
1answer
64 views

Are the very hyperlows closed under join?

Call $X$ very hyperlow if $\mathcal{O}^X \le_T \mathcal{O}$, where $\mathcal{O}$ is your favorite $\Pi^1_1$-complete set. Note: Turing reducibility, not hyp-reducibility. Observe that this is a (...
1
vote
2answers
228 views

Impredictable subsets of $\mathbb{N}$

(I previously asked a similar question on cstheory.SE; I have simplified the notion, which presumably changes it but does not change the key properties I'm interested in.) This is about a strange ...
4
votes
0answers
155 views

When is validity definable in $L_\alpha$?

Below, $\alpha$ is a countable p.r.-closed ordinal $>\omega$. Let $\mathcal{L}_\alpha=\mathcal{L}_{\infty,\omega}\cap L_\alpha$ (note that this is not the same as $\mathcal{L}_{\omega_1,\omega}\...
2
votes
1answer
185 views

The measure of ideals generated by random reals

We assume that for every real $x$, $L[x]$ only contains countably many reals. Given a set $X$ of reals, then $L$-ideal generated by $X$ is the smallest set $I$ of reals so that For any reals $x\in ...
5
votes
1answer
156 views

How far does this restricted definition on $\mathcal{O}$ goes?

$\mathcal{O}$ notation describes an onto function $f:\mathcal{O} \rightarrow \omega_{CK}$. In calculating all values $n \in \mathbb{N}$ such that $f(n)=\alpha$, when $\alpha$ is a limit, all indexes $...
2
votes
1answer
151 views

Detecting comprehension topologically

This question basically follows this earlier question of mine but shifting from standard systems of nonstandard models of $PA$ to $\omega$-models of $RCA_0$. For $X$ a Turing ideal we get the map $c_X$...
0
votes
1answer
157 views

Combinatorially defined effectively closed set

Is there a combinatorially defined, nonempty effectively closed set $Q\subseteq 2^\omega$ such that all members of $Q$ are incomputable? Combinatorially defined means that the definition of $Q$ does ...
1
vote
2answers
209 views

The “higher topology” of countable Scott sets

Fix some computable bijection $b$ between $\omega$ and $2^{<\omega}$. For $r\in 2^\omega$, let $$[r]=\{f\in 2^\omega: \forall\sigma\prec f(b^{-1}(\sigma)\in r)\}$$ be the closed subset of Cantor ...
0
votes
0answers
32 views

Is every productive set not Martin-Lof random?

every productive set is not Martin-Lof random,and so are some immune set.Therefore,do we have to have a definition for productive sets and such immune set which is different from Martin-Lof ...
1
vote
1answer
63 views

Non-relativized, Computable and Schnor randomness w.r.t a measure

Riemann and Slaman have some great work classifying what reals are 1-random with respect to a measure $\mu$ relative to $\mu$. In that paper they cite Levin and Kautz (but not to refs I can find) for ...
0
votes
1answer
61 views

Kurtz randomness and supermartingales with infinite *limit*

Suppose you replace the usual success conditions for a supermartingale (lim sup is infinite) with the requirement that the actual limit is infinite, e.g. a supermartingale $B$ succeeds on $X \in 2^\...
9
votes
0answers
156 views

Topology is to semi-decidability, coarse structures are to what?

There is a folklore correspondence between topology as semi-decidability amongst computer scientists, which is explained in places like: The monograph Synthetic Topology: of Data Types and Classical ...
7
votes
1answer
280 views

Does Higman's embedding theorem hold inside group varieties?

Suppose $\mathfrak{U}$ is a variety of groups. Let's define $F_n(\mathfrak{U})$ as relatively free groups in $\mathfrak{U}$. Suppose $G \in \mathfrak{U}$ is a finitely generated group. We call $G$ ...
0
votes
0answers
112 views

Is there a standard way to relativize algorithmic complexity constructively?

Given an index set $A$ of indices that compute some (class of) structures such that $A$ is complete in the class $ \Pi^0_n$ in the arithmetical hierarchy, let’s say we want to determine the ...
6
votes
1answer
270 views

“Robinson arithmetic” for (some) levels of $L$?

I'll write "$\mathcal{L}_\alpha$" for the fragment $\mathcal{L}_{\infty,\omega}\cap L_\alpha$. Say that a countable admissible $\alpha$ is Robinsonian if there is some sentence $\varphi\in\mathcal{L}...
5
votes
0answers
253 views

The expressiveness of functions computable on trees

Motivation: Let's define a function computable on a $k$-ary tree as a function composed with simpler computable functions defined at each node such that a function of this kind defined on a binary ...
1
vote
0answers
90 views

Does relationship between c.e.set, productive set, immune set, ML-random set exist between sets of class of other level

Is relationship between c.e.set, productive set, immune set, ML-random set similar to relationship between polynomial complexity set, polynomial complexity-productive set, P-immune set, P-random set?
8
votes
0answers
204 views

Large “computably un-simplifiable” computable well-orderings

Question Suppose $A,X$ are computable well-orderings. Say that $A$ is $X$-unsimplifiable if there is no computable well-ordering $B$ whose ordertype is strictly less than that of $A$ but such that ...
3
votes
1answer
311 views

Is the Hilbert space-filling curve bijective over computable numbers?

The Hilbert curve is a continuous space-filling curve that maps $I$ to $I^n$ where $I$ denotes the unit interval [1]. Like all other space-filling curves, it is not one-to-one. I am wondering if the ...
7
votes
0answers
170 views

Turing-independent joins

Define $Y \subseteq 2^{\omega}$ to be Turing independent if for every finite $F \subseteq Y$ and $y \in Y \setminus F$, the Turing join of $F$ does not compute $y$. Define $X \subseteq 2^{\omega}$ ...
0
votes
1answer
100 views

Are all $P$-noncomputable sets $P$-random? [duplicate]

$P$ means polynomial complexity. $S_p$ is class of all $P$_random sets, and $S_{pc}$ is class of all $P$ incomputable sets, is $S_{pc} \setminus S_p$ empty? If not empty, any example? what is the ...
3
votes
1answer
239 views

Relationship between P-noncomputable and P-random sets

$P$ means polynomial complexity. $S_p$ is the class of all $P$_random set, and $S_{pc}$ is the class of all $P$ incomputable sets, is $S_p \bigcap S_{pc}$ empty? If not empty, any example? what is ...
3
votes
0answers
277 views

Understanding a part of Friedberg’s Priority Argument Paper

This is Richard Friedberg’s original 1957 proof of the Friedberg-Muchnik Theorem, the origin of the ground-breaking priority argument. (The result proven is that there are two recursively enumerable ...
1
vote
1answer
117 views

Index sets and extensional many-one reductions

Let $\varphi_0,\varphi_1,\varphi_2,\dots$ be an acceptable programming system. A function $f$ is extensional if, for all $x$ and $y$, $\varphi_x=\varphi_y$ implies that $\varphi_{f(x)}=\varphi_{f(y)}$....
-1
votes
2answers
220 views

Do all non-computable functions grow faster than computable functions?

Do all non-computable functions grow faster than computable functions? In Does the Busy Beaver function grow faster than the Tree function?, the informal proof hinges on non-computable functions such ...
4
votes
1answer
367 views

Which ordinal is larger, the supremum of ordinals writable by iterated Infinite Time Turing Machines or the smallest $\Sigma_2^1$-reflecting ordinal?

The ordinal $\tau_1$ corresponds to $\lambda^{\textit{it}}$ (the supremum of all ordinals writable by iterated ITTMs) — see Definition 3.1 in the paper “ITTMs with Feedback” [Robert S. Lubarsky]. ...
3
votes
1answer
132 views

Is checking whether a compact $\Pi^0_1$-class is nonempty $\Sigma^1_1$-hard?

This question is about compact (but not necessarily effectively compact) $\Pi^0_1$-classes in Baire space. If I am given an index for a $\Pi^0_1$-class, and assured that it is compact, is determining ...
27
votes
7answers
4k views

Decision problems for which it is unknown whether they are decidable

In computability theory, what are examples of decision problems of which it is not known whether they are decidable?
2
votes
0answers
92 views

When can all elements of $[A\to B]$ can be represented as computable functions?

(crosspost from math stackexchange) While working through Barendreght's book on the Lambda Calculus, and Abramsky's notes on Domain Theory, I had the following realization: It's often stated that ...
1
vote
0answers
65 views

Existence of limit computable map

Is there a limit computable function $\Phi$ with the following properties? Let $T\subset \mathbb{N}^{<\mathbb{N}}$ be a tree (coded as its characteristic function) and $f\in\mathbb{N}^\mathbb{N}$ ...
3
votes
1answer
164 views

Is self-escaping without self-dominating possible?

For a countable structure $\mathcal{S}$, let the cospectrum of $\mathcal{S}$ be the set $CS(\mathcal{S})$ of reals (non-uniformly) computable in every copy of $\mathcal{S}$ (we can also make sense of ...
5
votes
0answers
151 views

Weaker versions of Gandy ordinals

Gostanian's paper "The next admissible ordinal" (see https://www.sciencedirect.com/science/article/pii/0003484379900251 ), is concerned with the supremum of the $\alpha$-recursive ordinals for various ...

1
2 3 4 5
14