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
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{...
Joshua Grochow's user avatar
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 { ...
Christopher King's user avatar
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 ...
TomHardCoder's user avatar
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 ...
Ethan Splaver's user avatar
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 ...
Yuval's user avatar
  • 21
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 (...
lyrically wicked's user avatar
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 ...
Max CYLin's user avatar
  • 151
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 ...
Dino Rossegger's user avatar
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)$ ...
paul Monsky's user avatar
  • 5,412
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 $(...
Dominic van der Zypen's user avatar
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 = \...
Valery Isaev's user avatar
  • 4,410
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 ...
Andrew Polonsky's user avatar
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 ...
Vladimir Slepnev's user avatar
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 ...
Arnold Neumaier's user avatar
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 ...
N. Virgo's user avatar
  • 1,316
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 ...
SSequence's user avatar
  • 861
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 ...
SSequence's user avatar
  • 861
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 ...
Max CYLin's user avatar
  • 151
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 ...
Noah Schweber's user avatar
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)$?
Christopher King's user avatar
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 ...
Talia Ringer's user avatar
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 ...
user avatar
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 ...
Joel David Hamkins's user avatar
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 ...
Noah Schweber's user avatar
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 ...
Noah Schweber's user avatar
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 ...
Jérôme Verstrynge's user avatar
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 ...
grok's user avatar
  • 2,489
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, \...
Christopher King's user avatar
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 ...
Sam Eisenstat's user avatar
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 ...
Christopher King's user avatar
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]$ ...
Hans-Peter Stricker's user avatar
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 ...
kakaz's user avatar
  • 1,596
-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 ...
Dominic van der Zypen's user avatar
-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 ...
XL _At_Here_There's user avatar
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. ...
喻 良's user avatar
  • 4,191
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 ...
Fedya's user avatar
  • 924
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 ...
Erfan Khaniki's user avatar
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>...
Dominic van der Zypen's user avatar
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. ...
Dawid K's user avatar
  • 139
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 $...
Lwins's user avatar
  • 1,531
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 ...
Holland's user avatar
  • 101
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 ...
XL _At_Here_There's user avatar
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 ...
Dmytro Taranovsky's user avatar
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 ...
Noah Schweber's user avatar
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. ...
Mikhail Katz's user avatar
  • 15.1k
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 ...
Frode Alfson Bjørdal's user avatar
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^{\...
Joel David Hamkins's user avatar
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 ...
XL _At_Here_There's user avatar
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 ...
Noah Schweber's user avatar
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}$ ?...

1
7 8
9
10 11
20