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.
974
questions
26
votes
2
answers
1k
views
Is the cohomology ring of a finite group computable?
Is there an algorithm which halts on all inputs that takes as input a finite group ($p$-group if you like) and outputs a finite presentation of the cohomology ring (with trivial coefficients $\mathbb{...
1
vote
0
answers
202
views
Lowest Turing degree that allows a Turing machine to tell whether $\operatorname{Con}(PA)$?
Let $T$ be a given turing machine. We say that $T$ decides $\operatorname{Con}(PA)$ if $PA + \operatorname{Con}(PA) \vdash T \text { accepts}$ and $PA + \lnot \operatorname{Con}(PA) \vdash T \text { ...
1
vote
1
answer
112
views
function application [closed]
Let the function cane and its auxiliary helping function down be the smallest functions satisfying the following requirement.
For every x∈ℕ, for every y∈ℕ, and for p=(x,y), all of the following ...
2
votes
1
answer
72
views
Name for "partially complete" invariants in classification problems?
For any equivalence $\sim$ on some collection of objects $C$ consider the problem of trying to determine if two arbitrary objects $x$ and $y$ in $C$ are equivalent i.e. if $x\sim y$ now by definition ...
2
votes
0
answers
145
views
what is the relationship between the complexity of a function and the complexity of it's graph set?
Given $f: \omega \rightarrow \omega$ , what is the relationship between the following two notions:
(i) the computational complexity of f (in the standard sense, say with naturals represented in ...
3
votes
2
answers
346
views
Can all lengths of shortest non-halting inputs of all Turing machines be limited by the Busy Beaver applied to the corresponding numbers of states?
Let $E_1$ denote the infinite enumerated collection of two-symbol (0 as blank symbol and 1 as non-blank symbol) one-tape (...
9
votes
1
answer
481
views
Axiomatizable $\exists \forall$ theory
I have been thinking the following problem proposed by my friends for a long time.
Let $\mathcal{L}$ be the first-order language of theory of rings and let $K$ be the class of algebraic number ...
4
votes
1
answer
142
views
Kruskal's tree theorem and $\Pi_1$ sentences of linear orderings with finitely many constants
In their paper "Theories with recursive models" [1] Lerman and Schmerl used a version of Kruskal's tree theorem about finite n-augmented trees.
An n-augmented tree is a tree T together with $n$ unary ...
7
votes
0
answers
97
views
Deciding when certain elements of $L[[x]]$, coming from recursions, are algebraic over $L(x)$
Let $L$ be a finite field of characteristic $2$. Suppose that for some $k > 0$ we are given elements $A(0),\, A(1), \dots, \, A(k-1)$ and $c(0),\, c(1), \dots,\, c(k-1)$ of $L[t]$. Define $A(n)$ ...
4
votes
0
answers
161
views
Tileability and computabilty
Let $n>2$ be an integer. We consider $n$ pairs $(x_1,y_1),\dotsc,(x_n,y_n)$ in $\mathbb{N}^2$, and the polygon defined by drawing a straight line from $(x_k, y_k)$ to $(x_{k+1},y_{k+1})$ and from $(...
8
votes
0
answers
151
views
Is every total computable function definable by a strongly total lambda term?
Every computable (total) function $f : \mathbb{N} \to \mathbb{N}$ is definable in untyped pure lambda calculus in the sense that there is a term $F$ such that, for every Church's numeral $c_n = \...
8
votes
1
answer
307
views
Is every total computable function definable by a normalizing lambda term?
$\newcommand{\nat}{\mathbb{N}}$
$\newcommand{\then}{\ \Longrightarrow\ }$
A partial function $f : \mathbb{N} \to \mathbb{N}$ is said to be $\lambda$-definable if there is a term $F \in \Lambda$ such ...
1
vote
0
answers
62
views
Predicting even bits with the universal prior
If the universal prior is fed a sequence where all even bits are 0 and all odd bits are drawn from some computable distribution, it will eventually become near-certain that the next 1000 even bits are ...
4
votes
0
answers
346
views
minimum size of undecidable quadratic diophantine problems
According to Matiyasevich, the existence of integer solutions of systems of polynomial equations with integer coefficients is undecidable. By introducing additional variables substituting factors of ...
27
votes
3
answers
2k
views
Defining computable functions categorically
Computable functions may be defined in terms of Turing machines or recursive functions, or some other model of computation. We normally say that the choice doesn't matter, because all models of ...
0
votes
0
answers
135
views
Elementary Question Regarding Classification of some Subsets of $\mathbb{N}$
The question is regarding a few easily described subsets of $\mathbb{N}$. I have difficulty identifying which classification they fall into. These certainly feel like questions that would be present ...
6
votes
2
answers
692
views
Reasoning Using Countable Subsets of Real Numbers
The purpose of my question is trying to understand whether, in some cases, we can achieve greater certainty of reasoning (say when dealing with statements about natural numbers, integers or rational ...
2
votes
0
answers
212
views
The elementary theory of finite commutative rings
I have wondered the decidability of elementary theory of finite commutative rings. Since we know that the elementary theory of finite fields is decidable shown by J.Ax (The Elementary Theory of Finite ...
9
votes
1
answer
705
views
Can the Turing degrees be linearly ordered?
Assuming the axiom of choice, every set can be linearly (indeed, well-) ordered. However, without choice this can fail, as witnessed most drastically by the consistency of amorphous sets. More ...
17
votes
1
answer
672
views
Would an oracle for Rayo's function let you compute a model of $(V, \in)$?
Working in Kelly-morse set theory, let $R$ be an oracle that can compute Rayo's function. Can $R$ compute a countable model $M = (\mathbb N,\in_M)$ that is elementary equivalent to $(V, \in)$?
1
vote
1
answer
282
views
Is Calculus of Constructions type inhabitance semi-decideable?
I'm wondering if type inhabitance for the calculus of constructions is semi-decideable. I know the following:
System F inhabitance and, correspondingly, second-order unification are semi-decideable
...
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 ...
19
votes
2
answers
1k
views
For a computable binary tree, is having no computable branches the same as having no probabilistic algorithm for producing branches?
It is a classical result of computability theory that there is a
computable infinite binary tree $T\subset 2^{<\omega}$ with no
computable infinite branch.
One way to construct such a tree is to ...
9
votes
0
answers
295
views
Moschovakis' discovery of E-recursion
E-recursion is a notion of generalized computability theory which seeks to extend computations to allow arbitrary sets as inputs. In contrast with e.g. $\alpha$-recursion, it disallows unbounded ...
3
votes
0
answers
98
views
Reducibilities: Muchnik versus Medvedev-mod-parameters
By "structure," I mean "countable first-order structure in a computable language." And I'm comfortable with whatever set-theoretic hypotheses make things most interesting, should such things be ...
12
votes
2
answers
2k
views
Proof there is no algorithm to compute the intersection of a line and sinusoidal wave?
There is obviously a set of situations where one lack an algorithm to compute the exact solution of an equation via symbolic manipulation only, for example ...
5
votes
2
answers
224
views
Different notions of computable binary sequence
The standard definition of computability, for a sequence $s\in\{0,1\}^\omega$, is that there is a Turing machine outputting $s[i]$ on input $i$.
I'm looking for strengthenings of this notion; for ...
5
votes
1
answer
268
views
Is there an oracle that can compute something iff it is computable in every countable model that is equivalent to $(V, \in)$?
Let us work in Kelly-morse set theory, so we can talk about $V$. For some model $M=(\mathbb N, \in_M)$ that is elementary equivalent $(V, \in)$, we can have an oracle that corresponds to $(\mathbb N, \...
10
votes
0
answers
230
views
Can we internalize topological fixed point theorems in an effective topos?
Reflective oracles are a kind of Turing oracle that give stochastic answers about the outputs of Turing machines. This works in a self-referential way, where they can answer queries about Turing ...
2
votes
2
answers
520
views
Connection between countable ordinals and Turing degrees
$\omega^{CK}_1$ is the supremum of all the recursive ordinals, where an ordinal $\alpha$ is recursive if there is a computable ordering of a subset of the naturals with order type $\alpha$.
For a ...
0
votes
0
answers
92
views
Name and theory of multi-valued functions $F:\mathbb{N}^k \rightarrow \mathbb{N}^l$
In computability theory there are considered mostly single-valued functions $f:\mathbb{N}^k \rightarrow \mathbb{N}$. (Let $\mathbb{N}$ be a placeholder for $\mathbb{N}$ or any initial segment $[0,n]$ ...
2
votes
1
answer
170
views
Internal operations on uncomputable functions
Is there know set of operations for which uncomputable functions are, let's name it down-unclosed? I mean a set of operations which takes two ( or more) uncomputable functions and return computable ...
-1
votes
1
answer
67
views
Computability of a relation connected to the discrete logarithm [closed]
Informally speaking, I was wondering whether the relation
$a^k \equiv b \text{ (mod } n)$ for some $k,n$
is computable. More formally: Let $\mathbb{N}$ denote the set of the positive integers and ...
-1
votes
1
answer
400
views
Conversion of logic formula into algebraic formula
We know formula of boolean algebra in canonical disjunctive normal form has or may be converted to Zhegalkin polynomial.
Is there any approach to convert first order formula into algebraic function ...
20
votes
1
answer
977
views
About $\omega_1^{CK}$
Here we use $\omega_1^{CK}$ to denote the least nonrecursive ordinal. The following theorem is well known.
$\mathbf{Theorem}$ $\omega_1^{CK}$ is an admissible ordinal.
But its proof seems weird. ...
3
votes
1
answer
203
views
How does the minimal size of a rational solution to a system of polynomial equations depend on parameters?
The undecidability of Hilbert's tenth problem implies the following (there is a stronger statement here, Theorem 9):
For any computable function $f$, there is a family of integer polynomials (where ...
5
votes
0
answers
104
views
Collapsing the Exponential time Hierarchy with a complete language as oracle
It is known that $\mathsf{P^A=NP^A}$ is true for every $\mathsf{EXP}$ complete language $\mathsf{A}$. The question is the whether the similar things hold for Exponential time Hierarchy.
Is there ...
2
votes
2
answers
164
views
Decidability of matrix problem in ${\mathbb Z}/p{\mathbb Z}$
Let $p$ be a prime number, $n$ be a positive integer, and let ${\mathbb Z}_p^{n\times n}$ denote the set of $n\times n$-matrices over ${\mathbb Z}/p{\mathbb Z}$.
Suppose we are given an integer $m>...
1
vote
0
answers
56
views
How to translate the triviality of computable Pareto optimality?
I asked this question on regular Math, and got the "Tumbleweed" badge for it (basically, it was ignored). I hope to get a better (any) response here.
I recently stumbled upon a paper relating to AI. ...
0
votes
0
answers
114
views
Is there a concrete statement unprovably true in ZFC? [duplicate]
I am new to mathematical logic so that maybe my problem is naive.
Consider a statement "$\forall n \in \Bbb{N},\ P(n)$" with a "checkable" property $P(n)$. In other words, there is a turing machine $...
10
votes
2
answers
479
views
What subsets of a set of integers can compute it?
For $x, y \subseteq \omega$,
(a) We write $x \leq_T y$ if $x$ is Turing reducible to $y$.
(b) We write $x \leq_L y$ if $x \in L(y)$ where $L(y)$ is the smallest model of ZFC that contains all ...
0
votes
0
answers
216
views
whether the quotient of continued fraction of algebraic irrational number is bounded or not is similar or equivalent to Collatz conjecture?
I vaguely recall that whether the quotient of continued fraction of algebraic irrational number is bounded or not is similar or equivalent to Collatz conjecture, could any one give the reference? or ...
2
votes
1
answer
429
views
Cardinal Register Machines
A cardinal register machine is like an ordinal register machine but with branching based on cardinal equality rather than ordinal equality. What is the complexity of the halting problem for cardinal ...
5
votes
1
answer
290
views
A game with boldface strength
This is a problem which has been bothering me for a while now; it doesn't seem inherently too hard, but I haven't been able to make any real headway, so I'm putting it out in the open since at this ...
8
votes
2
answers
731
views
Paul Cohen on genesis of method of forcing and mathematical similarities
We have on record Paul Cohen's comments on being inspired by issues of formalizing algorithms in number theory (this needs to be verified as per comment) as well as related remarks on computability. ...
0
votes
0
answers
215
views
Does Bounded Arithmetic, $I\Delta_0$, prove the Recursion Theorem?
Compare my question Does Robinson Arithmetic already entail the Recursion Theorem. I would find it desirable and interesting if $I\Delta_0$ could be extended with a comprehension principle CP stating ...
5
votes
1
answer
345
views
Is $n$ uniformly computable from an oracle for the $n^{\rm th}$ jump $0^{(n)}$?
This is a little curiosity that came up in a project I am working on, and I thought someone might have a nice way to see the answer.
Question. Can we uniformly compute $n$ from an oracle for the $n^{\...
3
votes
2
answers
737
views
Is any Cauchy sequence for completion of rational semicomputable?
For the definition of a semicomputable real, see An Introduction to Kolmogorov Complexity and its Applications by Li and Vitanyi (1997). In fact, it is not true that every Cauchy sequence for ...
8
votes
0
answers
183
views
Using van de Wiele's characterization as a definition?
This fall I'm teaching a class on generalized computability theory (broadly construed). One thing I want to talk about briefly is E-recursion.
Now, E-recursion is generally defined in terms of the ...
20
votes
2
answers
2k
views
Any important consequences with presupposition of $\mathbf{P} \neq \mathbf{NP}$
As we know, there are lots of consequences with the presupposition of the Riemann Hypothesis.
Similarly, are there any important consequences with the presupposition of $\mathbf{P} \neq \mathbf{NP}$ ?...