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
1
answer
177
views
Does there exist a geometric morphism between the effective and topological topoi? Does one arise from synthetic topology?
I'm presenting in final projects for my computability and computational topology courses on the connections between computability, continuity, and logic. As a mathematician/unmentored baby logician ...
- 48k
-3
votes
1
answer
115
views
why $L=\{\langle M\rangle\mid M \text{ is a TM that accepts all even number}\} \notin \text{RE}$ [closed]
$L=\{\langle M\rangle \mid M \text{ is a TM that accepts all even number}\}$
hello everyone I anderstennd why $L\in \text{coRE} $ b but I don't understand why $ L\notin \text{RE}$
I Have proved that $ ...
- 225k
5
votes
0
answers
192
views
Is it decidable whether a statement about reals (in the language of ordered rings) is constructively provable?
The language of ordered rings is a first-order language with operators for $+$, $-$, and $\cdot$, constants for $0$ and $1$, and relations for $<$, $=$ and $>$.
To decide whether such a ...
- 5,821
11
votes
5
answers
3k
views
Difference between constructive Dedekind and Cauchy reals in computation
If the Axiom of Countable Choice (ACC)
$$ \forall n\in \mathbb{N} . \exists x \in X . \varphi [n, x] \implies \exists f: \mathbb{N} \longrightarrow X . \forall n \in \mathbb{N} . \varphi [n, f(n)] $$
...
- 5,821
7
votes
2
answers
172
views
Why does Weihrauch reducibility make use of multi-functions?
This is probably a kinda dumb question, but why is Weihrauch reducibility defined in terms of multi-functions (i.e. why isn't it just the degree structure of regular functions under that reducibility)?...
- 3,969
5
votes
1
answer
463
views
Hilbert's and Gödel's expanded definition of "Recursive Function"
There is a very interesting comment in this post:
I must also make one terminological caveat: Hilbert, and later Godel, used the phrase "recursive function" in a way very different from the ...
- 48k
3
votes
1
answer
381
views
Hermit H-machines
I call an H-machine a machine that can be connected to turing machines and that takes as input a natural integer n and instantly returns the n'th digit of the mathematical constant H.
Is there a ...
- 225k
15
votes
10
answers
2k
views
Can you prove equivalence without being able to calculate it?
In mathematics we often seek to classify objects up to an equivalence relation, where two objects A and B are said to be equivalent if there exists a map $f:A\rightarrow B$ satisfying certain ...
- 225k
8
votes
1
answer
328
views
How bad can the recursive properties of finitely presented groups be?
Any finitely presented group naturally gives rise to an edge-labeled graph (the Cayley graph) and I am considering paths through this graph. Paths correspond to infinite sequences of generators, so ...
- 225k
16
votes
2
answers
1k
views
Is it decidable whether two real algebraic irrationals generate the same extension of the rationals?
For an algebraic number $\alpha$, let $f_\alpha$ denote its minimal polynomial. We can symbolically represent an algebraic number $\alpha$ by the tuple
$$
(f_\alpha, x, y, r) \in \mathbb{Q}[x] \times ...
- 2,391
2
votes
0
answers
86
views
Uniformization and functions on Turing degrees
Assuming Martin's Conjecture on functions between Turing degrees, is AD + DC consistent with existence of an $f:\mathcal{D}_t → \mathcal{D}_t$ of rank $Θ$ ?
$\mathcal{D}_t$ is the set of Turing ...
- 6,112
5
votes
1
answer
343
views
Infinite multiplicity set of continuous functions
Definitions:
Fix a function $f:\mathbb{R}\to\mathbb{R}$ such that $f$ obtains each value only finite (possibly $0$) number of times. We say $E \subset \mathbb{N}$ is the "multiplicity set" ...
- 225k
2
votes
1
answer
1k
views
When may function (meromorphic) be expanded as power series with coefficients of integers
Let $F$ be meromorphic function, with what properties may it be expanded as power series with coefficients of integers in such a form:
$$F=\sum_0^{\infty}a_i x^i,a_i\in \mathbb{N} \bigcup 0,\exists M \...
- 4,618
10
votes
0
answers
447
views
(A little bit) Beyond the E-recursive
The E-recursive functions are a particular generalization of classical recursion theory to the entire set-theoretic universe, $V$. They are defined via a schemes: see Sacks' $E$-recursive intuitions. ...
CommunityBot
- 1
5
votes
1
answer
389
views
Computational approach deciding whether a set of Wang Tile could tile the space up to some size
As an applied person, I'm facing one practical problem deciding whether a set of Wang tile could tile the plane periodically or aperiodically. Although both problems seem undecidable, but I'm on a ...
- 839
4
votes
1
answer
107
views
Does this hierarchy of fragments of $I \Sigma_1$ collapse?
Does anyone know whether the following hierarchy of fragments of
$\mathrm{I} \Sigma_1$ (or rather
$\mathrm{I} \Pi_1$) collapses or not?
Let $\Sigma^b_n$ denote formulas in the language of arithmetic ...
- 44.7k
31
votes
2
answers
6k
views
Is there a known Turing machine which halts if and only if the Collatz conjecture has a counterexample?
Some of the simplest and most interesting unproved conjectures in mathematics are Goldbach's conjecture, the Riemann hypothesis, and the Collatz conjecture.
Goldbach's conjecture asserts that every ...
- 11.4k
4
votes
1
answer
144
views
Does $A \leq_{\alpha} B$ imply $A \leq_{\beta} B$ for admissible ordinals $\alpha < \beta$?
My very superficial intuition of $\alpha$-recursion is that it replaces the tape in a Turing machine with $L_{\alpha}$ for some admissible $\alpha$, so that $L_{\alpha}$ functions as working memory. ...
- 1,725
10
votes
1
answer
269
views
Complexity of the set of models of TA
Recall that the theory of true arithmetic $TA$ is the theory of standard model of arithmetic $\mathcal N$. I am interested in the complexity of the set of countable models of $TA$ in the lightface or ...
- 515
7
votes
2
answers
619
views
Ideals generated by Turing independent sets
Recall that $X \subseteq 2^{\omega}$ is Turing independent if no $y \in X$ is computable from the Turing join of any finite subset of $X \setminus \{y\}$.
Question 1. Can we construct a Turing ...
- 1,725
67
votes
5
answers
10k
views
Decidability of chess on an infinite board
The recent question Do there exist chess positions that require exponentially many moves to reach? of Tim Chow reminds me of a problem I have been interested in. Is chess with finitely many men on an ...
- 225k
3
votes
1
answer
429
views
Decidability survives new constants
Let $L$ be a finite first order language
and let $M$ be an $L$-structure with universe $\mathbb{N}$
that interprets all $L$-symbols as recursive sets
(so $M$ is a recursive $L$-structure).
Let $L(c)$...
- 225k
3
votes
2
answers
151
views
Membership Provability in co-RE Sets
We're interested in recursive predicates $P(n)$ with RE range $R$ and non-RE complement $R^\prime$. For various $n \in R^\prime$ we may be able to prove that $n \in R^\prime$. For instance, if $P$ ...
- 225k
13
votes
6
answers
2k
views
Which model of computation is "the best"?
In 1937 Turing described a Turing machine. Since then many models of computation have been decribed in attempt to find a model which is like a real computer but still simple enough to design and ...
- 225k
2
votes
0
answers
71
views
Reverse mathematics on lightface $\Pi^1_1$-uniformization for unary relation
It is known that the following form of $\Pi^1_1$-uniformization is equivalent to $\Pi^1_1$-Comprehension over $\mathsf{ATR}_0$ (cf. VI.2.6 of Simpson's book) :
(Kondo's uniformization theorem) For ...
- 2,774
0
votes
1
answer
116
views
Integer quadratic representation subject to discriminant minimization algorithm
Let $f(x)=ax^2+bx+c$ and $f(x)=n$. Is there an algorithm to choose $a,b,c$ such that the discriminant is minimized? Where $a,b,c,n,x$ are all integers.
More concretely, is there an algorithm to find $...
CommunityBot
- 1
3
votes
0
answers
136
views
Lindström's theorem part 2 for non-relativizing logics
By "logic" I mean the definition gotten by removing the relativization property from "regular logic" — see e.g. Ebbinghaus/Flum/Thomas — and adding the condition that for every ...
- 19.1k
3
votes
1
answer
266
views
When is an upper bound on the longest irreducible program outputting something computable?
Given some way to to encode programs to strings with a finite alphabet, which we assume has a computable translation to/from Turing machines, a program is irreducible if no subsequence of it has the ...
- 2,979
3
votes
0
answers
161
views
Are all "reasonable" Gödel encodings isomorphic in some sense?
It is clear that many different Gödel numberings can work in Gödel's proof. Yet for the proof one just needs a few properties of how the numberings of related sentences are related, and I'm wondering ...
- 2,880
1
vote
1
answer
106
views
Solution to $a=e^t (t-r_1)(t-r_2)$ with Lambert $W$ function, where $r_1, r_2 $ are complex
Lambert $W$ works when $r_1$, and $r_2$ are real. However, I am trying to solve the equation when $r_1$, and $r_2$ are complex numbers.
8
votes
1
answer
257
views
What is known about these "explicitly represented" spaces?
Apologies if this is too low-level. A related question that I asked on the Math Stack Exchange got no answers after a year, so I thought it might be better to ask this one here.
The standard approach ...
- 4,491
1
vote
0
answers
67
views
EF-games with scrambling
This question is motivated both by the notion of zero-knowledge proofs and by general curiosity about versions of the infinitely-long Ehrenfeucht-Fraisse game which don't trivialize (= Duplicator win ...
- 19.1k
4
votes
1
answer
198
views
Is every compact, sober, second-countable space the image of $2^\omega$?
As a bonus, is every compact, $T_0$, second-countable space the image of $2^\omega \times \omega$?
As a further bonus, can we strengthen "image" to "quotient"?
My motivation for ...
- 4,491
13
votes
4
answers
3k
views
{transcendental numbers} \ {computable transcendental numbers}
I know Chaitin's constant Ω is not computable (and therefore transcendental). Are there other specific, known noncomputable numbers? I am trying to understand what distinguishes a computable ...
- 2,758
5
votes
0
answers
131
views
What is known about propositional realizability for the second Kleene algebra and related PCAs?
Short version: Various things are known about realizability of propositional formulas for Kleene's “first algebra” (i.e., $\mathbb{N}$), like examples of realizable but unprovable formulas, and some ...
- 30.2k
4
votes
1
answer
235
views
What is the theory of statements with a provably *bounded* realizer (according to PA)?
$\let\T\mathrm\def\kr{\mathrel{\mathbf r}}$This is a follow up to Kleene realizability in Peano arithmetic.
We can summarize the results from Emil Jeřábek's answer as follows:
\begin{gather*}
T_1 = \{ ...
- 11.4k
9
votes
4
answers
923
views
Are there two computable binary trees such that each has a branch not computing any branch through the other?
It is a well-known elementary classical result in computability theory that there are computable infinite binary trees $T\subset 2^{<\omega}$ having no computable infinite branch. (One can build ...
CommunityBot
- 1
3
votes
1
answer
125
views
A $\Pi^0_1$ class of $\alpha$-subgenerics for all $\alpha < w_1^{CK}$
In Harrington's mimeographed notes (see here) solving McLaughlin's conjecture he builds reals $f \in \omega^\omega$ which have the property of being $\alpha$-subgeneric defined as follows. He does ...
CommunityBot
- 1
19
votes
0
answers
791
views
"Compactness for computability" - does it ever happen?
Throughout, "computable structure" means "first-order structure in a computable language with domain $\omega$ whose atomic diagram is computable."
Say that a computable structure $...
- 19.1k
3
votes
2
answers
227
views
Question regarding $W$ as not hyperarithmetic
Consider the indexes of all ordinary programs generating functions from $\mathbb{N}^2$ to $\{0,1\}$. If we let $W$ be the set of exactly of all those indexes $e$ such that $\phi_e$ computes a total ...
- 19.1k
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,276
33
votes
3
answers
4k
views
Using Busy Beavers to prove conjectures
I've been pondering some stuff on Shtetl Optimized where Yedidia and Aaronson construct Turing machines that will only halt if (e.g.) the Riemann Hypothesis is false, or Goldbach's conjecture is false....
- 245
8
votes
1
answer
1k
views
Why don't Zeilberger and Gosper's algorithms contradict Richardson's theorem?
Richardson's theorem proves that whether an expression A is equal to zero is undecidable. A is in this case an expression, constructed from $x,e^x,\sin(x)$ and the constant function $\pi$ and $\ln(2)$ ...
- 125
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
14
votes
2
answers
1k
views
Church–Turing thesis for higher order functions
The Church–Turing thesis states that, simply speaking, any reasonable definition of "effectively computable functions" $\mathbb{N} \to \mathbb N$ agrees with the definition using Turing ...
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
2
votes
0
answers
121
views
Notes on Lachlan's monster
I have been trying to look for a reference I have seen in a paper called "R. Soare, Notes on Lachlan’s Monster Theorem" without success. I was wondering if anyone had a digital copy of them ...
- 743
13
votes
1
answer
604
views
Kleene realizability in Peano arithmetic
For completeness of MathOverflow and for clarity of the question, I will first recall a few things, including the the definition of Kleene realizability: experts can jump directly to the question ...
- 44.7k
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,821
4
votes
0
answers
193
views
Computational complexity of zeros of an analytic function
The work of Friedman and Ko, page 342, Corollary 4.3.1
states that all zeros of analytic polynomial time computable function are polynomial time computable, but for me that is not clear how it could ...
- 22.9k