# Questions tagged [computability]

Questions about Turing computability and recursion theory, including the halting problem and other unsolvable problems. Questions about the resources required to solving particular problems should be tagged (computational-complexity).

2,339 questions
Filter by
Sorted by
Tagged with
30 views

### How to define multivariable double recursive function

I have a question for those who are familiar with recursion theory. According to Wikipedia (https://en.wikipedia.org/wiki/Double_recursion), Raphael M. Robinson called functions of two natural number ...
28 views

### Definition of multiple recursive functions [closed]

According to Wikipedia, functions of two natural number variables $G(n, x)$ is double recursive with respect to given functions, if $G(0, x)$ is a given function of $x$. $G(n + 1, 0)$ is obtained by ...
142 views

### Can a decider return "Undecidable" on the Halting Problem?

So, I know there is no general algorithm for the halting problem, but I was curious if a three output decider could at least give us "an" output {0 if doesn't halt, 1 if halts, U if ...
52 views

### Reverse mathematics of characterization of compact spaces

It is known that, over $\text{RCA}_0$, the Heine-Borel theorem is equivalent to $\text{WKL}_0$ and that the Bolzano-Weierstrass theorem is equivalent to $\text{ACA}_0$. In general, a topological space ...
54 views

### Difference definable vs. computable

Is it true that a computable number or function is always definable, while the other way around is not? It seems so based on the following link: just want to confirm https://math.stackexchange.com/...
1 vote
61 views

23 views

### Equivalence result on recursive enumerable sets

I am reading the book of Robert Soare for recursive enumerable sets and degrees. There is the so called listing theorem, which stands that a set A is recursive enumerable if and only if A is not empty ...
70 views

### Proof for halting problem is recursively enumerable

So, I know the proof for Halting Problem is not recursive using diagonalization. We prove it using proof by contradiction. First we assume HP is recursive which implies there is a Total Turing Machine....
1 vote
60 views

### Could analog computers be used to solve a set of PDEs w/o the traditional numerical instability problems that come from discretizing the domain?

The question is simple. Could analog computers (for example, electrical analog computers) in effect avoid traditional numerical instability problems that come from solving a set of PDEs over a ...
430 views

### Why is incomputability weaker than Kolmogorov complexity?

Abbot et al. "Experimentally probing the algorithmic randomness and incomputability of quantum randomness" remark that "incomputability is a weaker property than Kolmogorov randomness&...
57 views

### Proving $\omega_1$ is measurable from Martin Measure being an ultrafilter

AD implies that each set of Turing degrees either contains a cone or is disjoint from one. It follows that the set of Turing degrees has a countably additive measure: $\mu(A) = 1$ if $A$ contains a ...
81 views

### Is the function sending a sentence to the diagonal of a sentence form extended over it, computable?

Is, the following function $h$ computable? Let $h: \mathbb N \to \mathbb N$ be the function defined by:$$h(\ulcorner s \urcorner) = \ulcorner D(E_s(v)) \urcorner$$ for each sentence $s$ in the ...
28 views

### Is $f$ primitive recursive in $g$ if $f$ does not eventually dominate $g$?

Let $f:\mathbb{N} \to\mathbb{N}$ be a monotonous numbertheoretic function, and let $g:\mathbb{N} \to\mathbb{N}$ be such that $$\forall m \exists n f(n)\leq g(n).$$ Is $f$ always primitive recursive in ...
1 vote
51 views

### Proof: Busy Beaver function is not calculable

I'm studying in a textbook and one exercise was to proof that the busy beaver function $B(n)$ is not calculable. My solution differed quite a bit from the one given in the textbook, so I wanted to see ...
105 views

### Does Curry-Howard correspondence mean that everyone who writes a program is doing intuitionistic mathematics?

As far as I know, the first statement of the correspondence is between two formal theories named simply typed lambda calculus and intuitionistic propositional logic, which maps types to formulas and ...
1 vote
41 views

### Infinite Recursion as the Intuitive Foundation for the Halting Undecidability Proof

all, I was wondering if my intuitive understanding of why the halting problem is undecidable is actually correct? TLDR: Halting problem is undecidable because it leads to infinite recursion and never ...
32 views

64 views

### Is there a transfinite version of Post's Theorem?

Let $\emptyset^{(n)}$ denote the $n$th Turing jump of the empty set. Post's theorem states: A set $B$ is $\Sigma^0_{n+1}$ if and only if $B$ is recursively enumerable by an oracle Turing machine with ...
115 views

### Highest theorems in the arithmetical / analytical hierarchy in terms of formula complexity

I am posing this question based on this answer which asserts that the Riemann Hypothesis is a $\Pi_1^0$ statement while $\mathsf{P}$-vs-$\mathsf{NP}$ is a $\Pi^0_2$ statement ("for every code for ...
60 views

1 vote
91 views

### Simplyfing $(\lambda y. z)((\lambda x. x x)(\lambda x. x x))$

I need to simplify this expression. $(\lambda y. z)((\lambda x. x x)(\lambda x. x x))$ However, what's interesting to me are two things: Should I start simplifying $((\lambda x. x x)(\lambda x. x x))$...
70 views

### Show that this set is $\Pi_1^0$-complete?
Let us call $A:= \{i \in \mathbb{N} \mid \varphi_i \ \text{is partial, computable and strictly increasing} \}$ and we want to show that $A$ is $\Pi_1^0$-complete (for the many-one reduction). First, ...
Let $A$ and $B$ be two random functions of binary variables (e.g., two probabilistic algorithms). Then, on input $x \in \{0,1\}^*$, $A(x)$ outputs $y \in \{0,1\}^{f_A(|x|)}$ with probability \$p_A(A(x) ...