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
1
vote
1answer
67 views

Computable functions with limited domains

In the developments I've seen of primitive recursive and computable functions, the functions always have codomain $\mathbb{N}$, but are allowed to have domain $\mathbb{N}^{m}$ for any natural number $...
1
vote
0answers
103 views

About functions primitive recursively definable using a $ \Sigma _ 1 $ oracle

In a discussion with one of my friends about degrees of computability, I was informed about something that was somehow new to me. As I'm not that much familiar with computability theory, I've ...
3
votes
2answers
85 views

Cupping and capping for 0’ relative to a recursively enumerable set

Is there an r.e. set $A$ such that 0’ is cuppable relative to $A$? What about cappable? This is equivalent to asking if there is an r.e. $A$ such that 0’ is one half of a pair of $A$ r.e. non-$A$ ...
2
votes
1answer
47 views

Does degree of jump determine degrees of relatively r.e. sets?

I’m mostly interested in this is the case where $A, \hat{A}$ are r.e. but the general case seems worth asking too. Suppose I have sets $A >_T \hat{A}$ with $A' \equiv_T \hat{A}'$. Does this imply ...
2
votes
1answer
42 views

Finding 1-generic paths through a tree $T \subseteq 2^{<\omega}$

Consider Cantor space $2^\omega$ with the standard topology generated by open sets $[\sigma] = \{ \sigma^\frown x: x \in 2^\omega \}$. If $A \subseteq 2^{<\omega}$ and $x \in 2^\omega$, we say $A$ ...
0
votes
0answers
88 views

Is a countable infinite union of $\Sigma_1$ sets is $\Sigma_1$? [migrated]

I’m reading Kunen’s book Foundations of mathematics. My question is whether a countable union of $\Sigma_1$ sets in $HF$ is also $\Sigma_1$ or not. I wonder if we can think $\Sigma_1$ sets as open ...
2
votes
1answer
145 views

Is there an algorithm on an infinite time Turing machine to compute a dense subset of $M_g$ for large $g$?

Denote by $M_g$ the coarse moduli space of connected smooth projective complex curves of genus $g$. If $g$ is a random large integer (e.g. $g=100$) does there exist an algorithm on an infinite time ...
4
votes
2answers
395 views

Is the collection of primitive recursive functions a lower set in the poset of computable functions?

If $g:\mathbb{N}\to\mathbb{N}$ is primitive recursive and $f:\mathbb{N}\to\mathbb{N}$ is computable such that $f(n) \leq g(n)$ for all $n\in \mathbb{N}$, does this imply that $f$ is primitive ...
2
votes
2answers
243 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
387 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
58 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
438 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
268 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
75 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
43 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
182 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
108 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
495 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
264 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
145 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
125 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
93 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
433 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
218 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
85 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
69 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
231 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
157 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
189 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
161 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
155 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
165 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
213 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
64 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^\...
10
votes
0answers
170 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
285 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
279 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
255 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
91 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
205 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
340 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
174 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
101 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
242 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
279 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
118 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
231 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 ...

1
2 3 4 5
14