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.
982
questions
6
votes
4
answers
287
views
What sets are "decidable from competing provers"?
Let $n$ be a member of $\omega$, which the omnipotent provers $Y$ and $N$ know. A Turing machine will be run starting with the $n$ already inputted, and the machine can have a natural number inputted ...
user5810
6
votes
2
answers
879
views
A Query regarding the Halting Problem (Omega): Halting Probability for Given Input Size
I was studying the Halting Problem in context of the Probability and had a few doubts regarding it. Hope someone could help me out.
I am aware of the probability of a Random program halting on a ...
- 81
6
votes
1
answer
873
views
The set of largest numbers definable by formulas in different lengths
Let $n=\phi(l)$ to be the largest number definable by a first order arithmetic formula $f(x)$ having length at most $l$. By "$n$ is definable by formula $f(x)$" I mean $\mathcal{N}\vDash f(a)$ iff $a=...
- 2,601
6
votes
3
answers
348
views
Intuition behind Kleene's “second algebra” $\mathcal{K}_2$
The “second Kleene algebra” $\mathcal{K}_2$ is defined, e.g. here on nLab, or in section 1.4.3 of van Oosten's book Realizability: an Introduction to its Categorical Side (2008), or as example 3.4 of ...
- 30.2k
6
votes
2
answers
269
views
Are there structures in a finite signature that are recursively categorically axiomatizable in SOL but not finitely categorically axiomatizable?
Recall that a structure $\mathcal{M} = \langle M, I^\sigma_M \rangle$ in a signature $\sigma$ is categorically axiomatized by a second-order theory $T$ when, for any $\sigma$-structure $\mathcal{N} = \...
- 1,135
6
votes
2
answers
2k
views
Are there proofs of Rice Theorem without using the undecidability of some problem?
Most proofs of Rice theorem seem to be based on the undecidability of
the halting problem. They are "reduction-based".
Are there "direct" elementary proofs, perhaps based on diagonalization?
I think ...
- 499
6
votes
2
answers
494
views
How does the Constructibility Degree of a real compare with its Turing Degree?
Specifically, is it the case that (for $a,b\in\omega^\omega$) $a$ $\leq_T$ $b$ implies $a$ $\leq_c$ $b$?
I suspect it might be trivial, but not knowing much Recursion Theory, it's hard to see how it ...
- 662
6
votes
2
answers
937
views
Is the distance function from a point to the Mandelbrot set computable?
There is at least one result saying that the Mandelbrot set is undecidable, and there might be more, but I think it (or they all) use real computation rather than Turing machines. This makes some ...
user5810
6
votes
2
answers
672
views
Relationship between non-standard computation and TM(oracle)?
We know that there are non-standard models of arithmetic, and in such models there are non-standard proofs of standardly unprovable sentences. Now, we can imagine a version of representability ...
- 743
6
votes
1
answer
347
views
computing abelianizations
Suppose I have a finitely presented group $G,$ and a subgroup $H$ of $G$ given by its finite generating set (given as words in the generators of $G.$ I want to know whether $H/[H, H]$ is finite. Is ...
- 95.6k
6
votes
3
answers
433
views
Is $0^{(\omega)}$ a minimal cover in the arithmetic degrees
Is it known if $0^{(\omega)}$ a minimal cover in the arithmetic degrees? In the Turing degrees to show that $0'$ (indeed $0^{(n)}$) isn't a minimal cover one uses the density of r.e. degrees. ...
- 2,633
6
votes
1
answer
327
views
What are these recursively defined sequences called?
Let $F(x,y)$ be a function of two variables, defined for all positive integers $x$ and $y$. Define a sequence $a_n$ recursively by setting $a_1 = 1$ and
$$a_n = \sum_{k=1}^{n-1} F(k, n-k) \cdot a_k ...
- 13.1k
6
votes
1
answer
629
views
Hilbert's tenth problem for equations with finitely many solutions
Is there a known example of a set $S$ of Diophantine equations such that
$S$ is computable;
it is a theorem that every equation in $S$ has (at most) finitely many solutions;
the function that maps an ...
- 78.7k
6
votes
1
answer
198
views
How often are forcing extensions of countable computably saturated models of $\mathsf{ZFC}$ computably saturated?
Recall that given a finite language $\mathcal{L}$, we say that an $\mathcal{L}$-structure is computably saturated (or recursively saturated) if for any computable set $\Sigma(\bar{x},y)$ of $\mathcal{...
- 10.3k
6
votes
1
answer
401
views
Computing the complex roots of a monic polynomial
The map from monic complex polynomials to the unordered tuples of their roots (each appearing according to its multiplicity) is computable. This seems to have been known for a long time, and with ...
- 4,491
6
votes
2
answers
250
views
Are there recursive sets $X$ with Property A that contain infinitely many incompressible strings?
Let us say a set $X$ satisfies Property A if$$\liminf_{n \to \infty} {{\left|X^{\le n}\right|}\over n} = 0.$$Are there recursive sets $X$ satisfying Property A that contain infinitely many ...
- 63
6
votes
2
answers
304
views
Recent trends in effective analysis
The references listed at http://en.wikipedia.org/wiki/Computable_analysis have all been published 30-15 years ago. Are the approaches which these references expose still up-to-date and relevant to the ...
user60665
6
votes
1
answer
195
views
Reference request: generalized randomness
There is a plethora of notions of randomness for Cantor space ($\phantom{}^\omega 2$) (Schnorr randomness, Martin-Löf randomness, weak 2-randomness, the various forms of higher randomness such as $\...
- 1,135
6
votes
1
answer
305
views
Given some recursive function, can we effectively associate it a polynomial as in the DPRM theorem?
I'm interested in the following assertion about the Davis-Putnam-Robinson-Matijasevich theorem
Given a recursive function $f:\mathbb{N}\rightarrow\mathbb{N}$, i.e. its index, we can effectively get ...
- 75
6
votes
1
answer
241
views
How similar are the c.e. degrees and the CEA(Cohen) degrees?
Given reals $A,B,X$, let $A\le_{T/X}B$ iff $A\oplus X\le_TB\oplus X$. For each real $X$ we can define a version of the c.e. degrees over $X$: we look at the preorder on $X$-c.e. reals given by $\le_{T/...
- 19.3k
6
votes
1
answer
210
views
A "dense" extension of the set of primitive recursive functions
Let $\mathcal{PR}$ be the set of primitive recursive functions. Let $\mathcal{PR}(f)$ be $\mathcal{PR}$ which we have amplified by adding (a recursive) $f$ the in the set of initial functions. To make ...
user39297
6
votes
1
answer
825
views
Rice's theorem in type theory
From the formula
$$\forall f\colon A\to A\,\exists x\colon A\,(f(x)=x)$$
we can get the scheme
$$\forall x\colon A\,(\phi(x)\vee\neg\phi(x))\Rightarrow\forall x\colon A\,\phi(x)\vee\forall x\colon A\,\...
6
votes
1
answer
278
views
Is 0' of PA degree relative to a non-low set?
Definitions:
A set $X$ is of PA degree relative to a set $Y$ if every infinite $Y$-computable binary tree has an infinite $X$-computable path.
A set $X$ is low if $X'$ is computable from $\emptyset'$....
- 394
6
votes
1
answer
408
views
An eventually different function adding no Solovay real nor dominating function?
Definitions
I believe set theorists have studied all of the following three notions in the context of forcing extensions of a model of ZFC, $M$ (hopefully the terminology is the standard one).
A ...
- 24.6k
6
votes
1
answer
246
views
Stronger exact pairs
Question: Suppose $\{a_n : n < \omega \}$ is a $<_T$-ascending sequence in $2^{\omega}$. Can we find $x, y \in 2^{\omega}$ such that for every $z \in 2^{\omega}$, the set of reals computable ...
- 61
6
votes
1
answer
170
views
Minimal degrees of structures
For this question, a structure means a first-order structure in a computable language with domain $\omega$; a copy of a structure $\mathcal{A}$ is a structure $\mathcal{B}\cong\mathcal{A}$.
Given a ...
- 19.3k
6
votes
1
answer
330
views
What is known about the boundary between Richardson's theorem and the Tarski-Seidenberg theorem?
Tarski proved that equalities and inequalities in can be decided over $\mathbb{R}[x].$ Richardson proved that adding composition with the sine and exponential functions caused the problem to become ...
- 8,994
6
votes
1
answer
769
views
Where does the deterministic simulation of non-deterministic ω-Turing machines fail?
An $\omega$-Turing machine is just a usual Turing machine $T=(Q,\Sigma,\Gamma,\delta,q_0,F)$ where $Q$ is the finite set of states, $\Sigma$ is the input alphabet, $\Gamma\supset\Sigma$ is the tape ...
- 2,442
6
votes
1
answer
302
views
Examples of "natural" finitely generated groups with an undecidable conjugacy problem
I am looking for natural groups with undecidable conjugacy problem. By natural, I mean that the word problem should be decidable, and the group should be given by some natural action. I know that $\...
- 6,337
6
votes
1
answer
224
views
"Partial-computably isomorphic" sets
For $A,B \subseteq \mathbb{N}$, define $A\sim B$ when there exist partial computable functions $f,g\colon \mathbb{N}\rightharpoonup \mathbb{N}$ such that $f$ is defined at least on all of $A$ and $g$ ...
- 30.2k
6
votes
1
answer
314
views
Finding limit-nondecreasing sets for certain functions
This is a question that arose a while ago in work with Damir Dzhafarov on some pieces of reverse mathematics. As far as I know, it has no deep significance; however, it feels like the sort of thing we ...
- 19.3k
6
votes
1
answer
256
views
Degree of unsolvability of finding a open approximation to a Borel set, given its Borel code
It is well known that every Borel set has the property of Baire. That is, for every Borel set $B$, there is an open set $U$ and a sequence of dense open sets $D_n$ such that for every $x\in \cap_n ...
- 1,601
6
votes
1
answer
508
views
Parameter-free effective cardinals
In the paper "Effective cardinals and determinacy in third order arithmetic" by Juan Aguilera, effective cardinals is defined.
I'm curious about its little variation, parameter-free ...
- 1,410
6
votes
1
answer
241
views
Is a function growing faster than any computable function necessarily independent of ZFC?
Let $\mathrm{BB}:\mathbb{N}\to\mathbb{N}$ be the Busy beaver function. Then we have the following.
Let $T$ be a computable and arithmetically sound axiomatic theory.
Then there exists a constant $n_T$...
- 61
6
votes
1
answer
193
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: ...
- 909
6
votes
2
answers
386
views
a variant of the Kleene tree
The (a?) Kleene tree is a computable (a.k.a. decidable) sub-tree of the full binary tree with no computable path. It is well-known.
I need a variant. (For those in the know, I need a c-bar which is ...
- 374
6
votes
1
answer
274
views
Disjoint sets of fixed points
Let $\phi$ be an acceptable programming system. For every recursive function $f$, let $(f)=\{x:\phi_x=\phi_{f(x)}\}$ the set of fixed points of $f$. Now, suppose that $f$ and $g$ are recursive ...
- 63
6
votes
1
answer
475
views
Probability that a Turing machine will nontrivially reduce a real
For a fixed Turing machine $\Phi_e$, what is the probability that it will reduce a given real to some less complex, yet still non-computable real?
More precisely: It is known that the set of reals ...
- 19.3k
6
votes
1
answer
359
views
Recursive Non-Well-Orders that are Sneaky, but not THAT Sneaky.
This is a variant on
Sneaky Recursive Non-Well-Orders
where it was asked
Is there a recursive function $f$ such that whenever $a\in\mathcal{O}$, $f(a)$ is a Turing index for a linear non-well-...
- 61
6
votes
1
answer
106
views
Sets meeting and avoiding computable sets
Call a set $X$ hesive if for every infinite computable set $C$, both $C \cap X$ and $C \setminus X$ are infinite.
It's not hard to see that every hyperimmune degree computes a hesive set, but this isn'...
- 2,678
6
votes
1
answer
235
views
A variant of the Busy Beaver function
Set $BB(k,n)$ to be the same definition as the Busy Beaver but where one is looking at all $n$-state machines, and the transition graph has at most $k$ "write 1" instructions. This may be a ...
- 6,100
6
votes
1
answer
498
views
Regularity properties of Turing-invariant and arbitrary sets of reals
The question whether Turing determinacy implies $AD$ is a well-known open problem. I was wondering if anything is known about the following analogous question:
Let $\Gamma$ be a regularity property (...
- 421
6
votes
1
answer
188
views
Finite-variable fragments of $\Delta_0$-formulas
Consider sets definable in the usual structure of arithmetic $(\mathbb{N},0,1,+,\times)$ by $\Delta_0$-formulas, i.e., formulas with bounded quantifiers. The quantifier alternation hierarchy has been ...
- 201
6
votes
1
answer
268
views
Deciding isomorphism between graphs which interpret in the pure set
I am interested in the following decision problem:
Given descriptions of two graphs $G,H$ which interpret in the pure set $\mathbb N=(\{0,1,2,\ldots\},=)$, decide whether $G$ and $H$ are isomorphic....
- 628
6
votes
1
answer
805
views
What can be done with computability logic that previous logic systems can't?
I've been reading a lot about computability logic lately and I'm superficially aware that it unifies classical, intuitionistic and linear logics.
What I'm seeking to know is:
Can computability logic ...
- 69
6
votes
1
answer
278
views
Need help in trying to understand an argument by V. A. Yankov on the nonrealizability of Scott's axiom
(This is really long because I give a lot of context, but you can skip right to the end where the excerpt I'm trying to make sense of is copied and translated.)
Background: I'm trying to understand ...
- 30.2k
6
votes
1
answer
278
views
What is the power of the “anti-halting” oracle?
Let me first ask the question, and then, as it may seem a bit cryptic, explain how it comes up (and whence the “anti-halting oracle” in the title):
Notations: we write $\langle m,n\rangle$ for a ...
- 30.2k
6
votes
1
answer
389
views
Reference request: a version of $\Sigma^1_1$ bounding for structures
There's a (fairly basic) fact I want to use in a paper I'm writing; it's not entirely trivial, so I don't feel comfortable just stating the result and moving on, but I don't have a citation for it. ...
- 19.3k
6
votes
0
answers
207
views
What are these non-classical versions of ZFC defined by realizability?
See Kleene realizability in Peano arithmetic for a similar question, but about PA instead of ZFC.
In the context of constructive set theory, consider two ways of defining realizability.
The first is $\...
- 5,831
6
votes
0
answers
121
views
An analogue of Scott sentences in the (mostly) computable realm?
Below, "structure" means "computable structure in a computable language." In particular, we do distinguish between isomorphic copies of the same structure.
Let $\mathcal{L}_{\...
- 19.3k