Skip to main content

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
1 answer
357 views

Natural Numbers

Let $L$ be a countable language and $M$ be a model of $L^N$ (the realization of $L$ in the natural numbers $N$) in which every recursive unary relation is expressible. Show that $M$ is not recursive.
Speltzu's user avatar
  • 255
-3 votes
1 answer
126 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 $ ...
NOYA GENDELMAN's user avatar
9 votes
1 answer
197 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 ...
Garrett Figueroa's user avatar
7 votes
0 answers
209 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 ...
Christopher King's user avatar
5 votes
1 answer
468 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 ...
Mike Battaglia's user avatar
7 votes
2 answers
182 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)?...
Peter Gerdes's user avatar
  • 2,633
2 votes
0 answers
88 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 ...
Dmytro Taranovsky's user avatar
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 ...
user918212's user avatar
  • 1,035
4 votes
1 answer
109 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 ...
Lukas Holter Melgaard's user avatar
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" ...
Kripke Platek's user avatar
7 votes
2 answers
621 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 ...
Fiona's user avatar
  • 71
2 votes
0 answers
73 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 ...
Hanul Jeon's user avatar
  • 2,774
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. ...
Zoorado's user avatar
  • 1,215
3 votes
0 answers
162 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 ...
Joshua Grochow's user avatar
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.
Hamed Elwarfalli's user avatar
3 votes
0 answers
137 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 ...
Noah Schweber's user avatar
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 ...
Noah Schweber's user avatar
4 votes
1 answer
199 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 ...
Robin Saunders's user avatar
5 votes
0 answers
133 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 ...
Gro-Tsen's user avatar
  • 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 = \{ ...
Christopher King's user avatar
3 votes
2 answers
229 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 ...
SSequence's user avatar
  • 861
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 $...
ReverseFlowControl's user avatar
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)$ ...
Martin Clever's user avatar
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....
schnitzi's user avatar
  • 463
2 votes
0 answers
122 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 ...
H.C Manu's user avatar
  • 743
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 ...
Trebor's user avatar
  • 1,031
6 votes
0 answers
208 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 $\...
Christopher King's user avatar
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 ...
Gro-Tsen's user avatar
  • 30.2k
3 votes
1 answer
272 views

Root finding algorithm for an analytic function

Given an analytic function $f(x)$. What is the best algorithm to find roots on the interval $[a,b]$ inside the radius of convergence> What is its complexity with respect to the length of input of ...
poeaqnwgo's user avatar
3 votes
1 answer
108 views

Kleene normal form theorem for r.e. relations proven in arithmetical theories

After reading the relevant chapters of Classical Recursion Theory (freely available from here), I have the following questions concerning Theorem II.1.10 (Normal form theorem) and Theorem IV.1.9 (...
CBuch's user avatar
  • 31
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 ...
Command Master's user avatar
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 ...
poeaqnwgo's user avatar
14 votes
1 answer
500 views

How exactly are realizability and the Curry-Howard correspondence related?

Consider, on the one hand: the Curry-Howard correspondence between, on the one hand, types and terms (programs) in various flavors of typed $\lambda$-calculus, and on the other, propositions and ...
Gro-Tsen's user avatar
  • 30.2k
7 votes
1 answer
311 views

Proving finiteness in Reverse Mathematics

In (second-order) Reverse Mathematics, a (code for an) open set $U\subset \mathbb{R}$ is given by two sequences of rationals $(a_n)_{n \in \mathbb{N}}, (b_n)_{n \in \mathbb{N}}$. The idea is that $U$ ...
Sam Sanders's user avatar
  • 3,977
4 votes
3 answers
370 views

Hyperarithmetically least elements in $\Pi^1_1$ sets

My question is: Do we have a hyperarithmetically $\le_H$-least real in any $\Pi^1_1$ set? That is Question. Suppose that $A$ is a non-empty $\Pi^1_1$ set. Then can we find a real $a\in A$ such that $...
Hanul Jeon's user avatar
  • 2,774
5 votes
0 answers
181 views

Complexity implications on computability

Are there any known links between complexity theory and computability theory by which I mean non-trivial theorems of the form: If NP $\neq$ co-NP then there is no strong minimal pair of r.e. sets or ...
Peter Gerdes's user avatar
  • 2,633
3 votes
0 answers
93 views

Comparing computable structures via Kleene and Skolem

Below, by "structure" I mean "computable structure in a finite language with domain $\omega$," and by "sentence" I mean "finitary first-order sentence containing no ...
Noah Schweber's user avatar
0 votes
1 answer
98 views

Is there a canonical mapping between countable transfinite ordinals and $\omega$? What about recursive ordinals?

Consider $\omega^2$. We can build a simple bijection between the ordinal and $\omega$ similarly to how the bijection between $\mathbb{Q}$ and $\mathbb{N}$ can be built. I was wondering if there is a ...
Guillermo Mosse's user avatar
1 vote
0 answers
111 views

Sudden drop in complexity class due to the more general correlations

Recently I was asking about the impact of the groundbreaking result MIP*=RE on logic and proof theory (see this discussion). Surprising as it is I got confused with the following: MIP* is a ,,quantum''...
truebaran's user avatar
  • 9,150
1 vote
1 answer
86 views

How large can a subset of computable reals, whose comparison function is computable, grow?

How large can a subset of computable reals, whose comparison function is computable, grow? For example, rational numbers are computable reals, and its comparison function is computable. As another ...
Hexirp's user avatar
  • 335
0 votes
0 answers
169 views

Can a model of "true computation" exist? What would be its consequences?

Analogous to the model of True Arithmetic, the model of "True Computation" is defined to be the set of all true first-order statements about Turing machines i.e. answers to elementary ...
symmetrickittens's user avatar
4 votes
0 answers
107 views

Decidability of whether two polynomial bijections generate a free group

I am wondering about the decidability of the following question: Given two polynomial bijections $f, g$ from the real numbers to the real numbers (with say rational coefficient just to simplify what &...
Sprotte's user avatar
  • 1,065
1 vote
0 answers
57 views

Are the lower elementary functions closed under limited recursion?

The lower elementary functions (also called Skolem elementary functions) are functions generated from the successor, modified subtraction, projection functions by the operations of composition and ...
Guozhen Shen's user avatar
  • 1,288
8 votes
2 answers
559 views

Turing degrees of sets separating two computably inseparable sets (theorems and antitheorems)

Let $A\subseteq\mathbb{N}$ be the set of Gödel codes of theorems of Peano arithmetic, and $B\subseteq\mathbb{N}$ be the set of codes of antitheorems (i.e, refutable statements, statements whose ...
Gro-Tsen's user avatar
  • 30.2k
10 votes
2 answers
431 views

Is the set of permissible numbers of models of various cardinalities computable?

This question arose in the comments to this question. Let $X$ be the set of pairs $(m,k)$ such that there is some (consistent complete countable first-order) theory $T$ with exactly $m$ models of size ...
Noah Schweber's user avatar
2 votes
1 answer
121 views

Splitting $\Pi^0_2$ Singletons?

Given a (non-computable) $\Pi^0_2$ singleton $Y$ are there Turing incomparable $\Pi^0_2$ singletons $X_0, X_1$ with $Y \equiv_T X_0 \oplus X_1$? What about the same question for arithmetic ...
Peter Gerdes's user avatar
  • 2,633
4 votes
1 answer
225 views

Can a halting oracle determine if a Turing machine is an ordinal?

For the sake of clarity, I am regarding a computable relation on $\mathbb{N}$ as a $2$-symbol ($0$ and $1$) Turing machine $T$ which halts on any initial binary string (which are interpreted as some ...
Sam Forster's user avatar
6 votes
1 answer
279 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 ...
Gro-Tsen's user avatar
  • 30.2k
3 votes
1 answer
122 views

The sequence of the power chromatic numbers $(\chi(G^n))_{n\in\mathbb{N}}$

For any finite, simple, undirected graphs $G, H$ we denote by $G\times H$ their categorical product. For any graph $G$ we let $G^1 = G$ and for $n\geq 1$ we let $G^{n+1} = G \times G^n$. It is easy to ...
Dominic van der Zypen's user avatar
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 ...
Peter Gerdes's user avatar
  • 2,633

1
2 3 4 5
20