Questions tagged [computability]

Question 1

There is a theorem that for a total function, it is recursive iff its graph relation is recursive. In other words, you can write the graph relation with only bounded quantifiers. What would be such a ...

Question 2

This question is based on the question Is it possible to formulate the axiom of choice as the existence of a survival strategy? (MathOverflow). Consider the following "computable giraffes, lion &...

Question 3

Question: Has it been proven that the following decision problem is algorithmically decidable? $$ P_\text{Collatz} := \text{Given $n \in \mathbb{N}_+$, does the Collatz-Iteration of $n$ eventually ...

Question 4

The standard definition of recursive enumerability is as follows: a set of natural numbers is recursively enumerable if there exists an algorithm which halts precisely on inputs which are elements of ...

Question 5

I’ve been reading about objective Bayesian theories lately and came upon the concept of universal priors and specifically, the Solomonoff prior. This seemed to answer my initial query about whether a ...

Question 6

In the book I read, PA degrees are defined as containing a completion of Peano arithmetic. I'm searching for a proof that PA degrees are closed upwards (which is non-trivial with this definition). ...

Question 7

I am reading Robert I. Soare's "Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets" for a directed reading course. I am having trouble ...

Question 8

I am currently working on a proof that $\mathrm{Inf}\leq_1\mathrm{Tot}$, where $$\mathrm{Inf}=\{e:\mathrm{Dom}\,\varphi_e \text{ is infinite}\} \quad \mathrm{Tot}=\{e:\varphi_e\text{ is total}\}$$ (...

Question 9

I am trying to prove that a certain function is partial recursive. Suppose we have fixed primitive recursive $g:\mathbb{N} \rightarrow \mathbb{N}$ and for each $d$ let $f_d:\mathbb{N}\rightarrow \...

Question 10

Let $\langle W_e : e\in\mathbb{N}\rangle$ be the standard effective enumeration of recursively enumerable (r.e.) sets, where $$ n\in W_e \;\Longleftrightarrow\; \exists s\;\big(\varphi_e(n)\ \text{...

Question 11

In Mihai Prunescu, Lorenzo Sauras-Altuzarra, and Joseph M. Shunia (2025), A Minimal Substitution Basis for the Kalmar Elementary Functions, the authors define a minimal generating set for the Kalmár ...

Question 12

The question is possibly related to this, but I don’t find a satisfactory answer there. Let $X$ be a set and $P(n, x)$ be a mere proposition for all $n: \mathbb{N}$ and $x: X$. The axiom of countable ...

Question 13

I am working with recursive functions on $\omega$. It is well known that these functions are representable, in the sense of the following definition: A function $f:\omega\to\omega$ is representable in ...

Question 14

I wanted to prove that Kleene's $\mathcal{O}$ is not computable without using the diagonalization trick, and was wondering if the following proof would work? Note: ordering = well-ordered set. Suppose ...

Question 15

Let $X$ be a proper variety over a global field $k$. Then we can find a model $\mathfrak{X}$ over a Dedekind domain $R$ of finite type. Every special fiber of $\mathfrak{X}$ is over a finite field, so ...

Stack Exchange Network

Questions tagged [computability]

Graph relation for the Ackermann Relation

Can countably many giraffes guess the color of their own scarf correctly if each may be mistaken about the color of finitely many scarves?

Is the Collatz map algorithmically decidable?

Recursively enumerable sets and the natural numbers

Can probability theory be made fully computable?

Upward closure of the PA degrees

Theorem 3.4 of Soare

Proving Inf is 1-reducible to Tot

Is function defined by infinite cases partial recursive?

Where is the relativized uniform complementor on r.e. indices stated explicitly (index-operator form)—existence for $\emptyset'$ and any minimality?

Can superposition alone generate the Kalmár elementary function $x^y$ from $⟨x + y, x \bmod y, 2^x⟩$?

Computational content of axiom of countable choice in HoTT

Recursive functions are $\Sigma_1$ in PA? [duplicate]

Proof without diagonalization that Kleene's $\mathcal{O}$ is not computable

When are $\ell$-adic betti numbers of varieties computable

Hot Network Questions