# Tagged Questions

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).

81 views

### Definable non-computable number which contain no information

We have three types of numbers AFAIK: a) Computable b) Definable and non-computable, but contains information about Halting of some turing machines, extractable in a computable way if you were given ...
108 views

### How to find an index of a computable function?

Is there an index $i$ such that $\phi_{p(i)}(0) = i + 2$, for a total computable function $p$? I know about the s-m-n theorem and fixed point theorem, and how to apply them to some basic functions ...
113 views

43 views

### Prove $A(x,y)= 2[x](y+3)-3$. Where A is the Ackermann-Peter function and [x] is x-th hyperoperator.

I've successfully proven $A(x,y)$ for some fixed x and any y with induction but I'm having a hard time proving this for any x and y. I think the next useful step would be proving $A(x,0)= 2[x]3-3$ ...
60 views

### $\alpha$-computable bounded subset of $\alpha$ is in $L_\alpha$

I would like to prove the proposition 1.12b from Chong, Techniques of Admissible Recursion Theory: Let $\alpha$ be an admissible ordinal. A subset $K \subseteq \alpha$ is in $L_\alpha$ ($\alpha$-th ...
41 views

### Computable problem

A mathematical problem is computable if there is an algorithm that decides/solves this problem, right? Can you give an example of such a problem?
74 views

### If $\Gamma$ is an infinite set of propositional formulas, is the statement: “$\Gamma$ is satisfiable” decidable?

Here, $\Gamma$ is satisfiable means that there exists a truth function $v$ such that $v(\gamma)=$ True for all $\gamma \in \Gamma$. I know that the set of all propositional formulas is countable (our ...
75 views

### What does it mean if a free algebra has an unsolvable word problem?

I wonder how hard identity testing (similar to polynomial identity testing) can be for a free algebra. I thought that in a certain sense, the problem should always be semi-decidable, because the free ...
53 views

### Recursive Enumeration of Total Recursive Functions vs Partial Recursive Functions

We have: Primitive Recursive $\subseteq$ Total Recursive Functions $\subseteq$ Partial Recursive Functions There are three points that appear at odds with eachother: 1) The primitive recursive ...
32 views

### Are Euler Bricks a Recursively Enumerable Set?

An Euler brick satisfies the Diophantine Equations: $a^2+b^2=d^2$ $a^2+c^2=e^2$ $b^2+c^2=f^2$ Where a,b,c,d,e, and f are integers. Has anyone proved the solutions are recursively enumerable? Or ...
133 views

### Non-zero solutions of the system

I have concluded to the following results: An homogeneous linear differential equation in the ring $\mathbb{C}[x]$ has a solution if at least one root of the characteristic equation is equal to $0$....
90 views

### Elimination of quantifiers

What does it mean that a theory admits constructive elimination of quantifiers? A theory admits elimination of quantifiers when each formula of the theory is equivalent to a quanifier-free formula, ...
31 views

### Deciding set of all Turing machine codes of TMs accepting languages of cardinality $\leq 10$.

Problem: I need to show that the following language is decidable and if not, if $S$ or $\overline{S}$ is partialy decidable language. $S=\{w_e\;|\;|L(M_e)|\leq 10\}$ That is set of all Turing ...
42 views

### Unprovable behavior of a turing machine

The wikipedia-article for the P-NP problem [1] says there are three possible answers to the P-NP-problem: $P=NP$ $P\neq NP$ $P=NP$ is independent of ZFC The third possible solution seems to be ...
40 views

### How could I design a turing machine that prints all natural numbers on its tape in order?

How one could implement a turing machine that prints all natural numbers of its tape in order. Two consecutive numbers are separated on the tape with the symbol #. The tape should look like this: #0#...
62 views

### Show that every finite subset of $\{0,1\}^*$ is recursive [closed]

How can I show that every finite subset of $\{0,1\}^*$ is recursive ?
36 views

### Explain why these sets are recursive or r.e.

A set $A \subseteq \mathbb N$ is recursive. Working from an informal idea of "computability" explain why the set $B = \big\{ x \in \mathbb N : \exists u,v \in A, u+v=x \big\}$ is recursive and the ...
31 views

### Using Church's thesis to show a certain simple function is computable.

I am not quite sure how to apply Church's thesis to the following problem to do with register machines: The function $E(e)$ is defined so that on input of a godel number $e$, the function returns the ...
45 views

### nocomputable function f such that x is not in the Halting Problem iff f ( x ) belongs to set of Kolmogorov-random strings

taking clue from this question set of Kolmogorov-random strings is co-re the paper mentioned in the above link talks about the non existence of a computable function how can I show that there is ...
115 views

### Is there a “computable” countable model of ZFC?

Question Assuming ZFC is consistent (has a model), does there exist a set $S$ and a binary relation $\in_S$ on $S$ that satisfy the following? $S \subseteq \{0,1\}^*$ (this is the Kleene star, and ...
66 views

### Is a Turing machine on an arbitrary (finite) alphabet equivalent to one on {0, 1}?

Brief context: I'm trying to understand why a Universal Turing Machine exists, on a tape with alphabet $\{0, 1\}$. I think I can see that a $3$-tape Turing machine can represent a Universal Turing ...
52 views

### not any computable function f such that x is not in the Halting Problem iff f ( x ) belongs to set of Kolmogorov-random strings

taking clue from this question set of Kolmogorov-random strings is co-re the paper mentioned in the above link talks about the non existence of a computable function how can I show that there is ...
30 views

### Compare a non-computable real number to a rational

Suppose we have a non-computable real number $p$. Can we determine for any rational $r$ whether $r \lt p$ or $r \gt p$? I think that if we could, than we could approximate $p$ by rationals from above ...
85 views

### set of Kolmogorov-random strings is co-re

given RC = {x : C(x) ≥ |x|} is a set of Kolmogorov-random strings. How can I show that RC is co-re I have been reading this paper What Can be Efficiently Reduced to the Kolmogorov-Random Strings?...
61 views

### Positive existential theory of an extension of the ring

When we know that the positive existential theory of a ring $R[x]$ in a language $L$ is undecidable, does it follow that the positive existential theory of $R[x,y]$ in the same language $L$ is also ...
24 views

### Show that the problem of deciding whether a Turing machine prints something is undecidable

I am unable to get the logic for showing that the problem of whether a Turing machine prints something is undecidable by showing that the halting problem reduces to it. Please guide me with this.
25 views

### The approximability of different NP-hard problems

I'm fairly new to the topic Computational Complexity and had the following question (I therefore apologies before hand for any poorly stated terminology). Suppose i have two optimization problems $A$...
49 views

### Abstract machines that compute primitive recursive functions

What it the simplest (least powerful) abstract machine that can compute primitive recursive sets, i.e. sets whose characteristic or indicator function is primitive recursive? f:\mathbb{N}\...
41 views

### Understanding AI through a complexity function

I've been trying to understand in light of a few apparent paradoxes for me. It appears reasonable that we could prove any mathematical problem that has a well defined answer can be solved by a ...
67 views

### Book on Curry-Howard Isomorphisms

I would like to learn about Curry-Howard Isomorphism because I want to know more about connections between computability and logic. I have already read book on first order logic and I know about ...
95 views

### What lies between primitive recursion and total recursion?

My understanding is that there are total recursive functions that are not primitive recursive, such as the Ackermann function. What classes of functions (or sets) lie between primitive recursion and ...
27 views

### How can I write a partial recursive function “maximum(x,y,z)”?

It is quite easy to write a partial recursive function "max(x,y)": 1.substraction1: substraction(x) = if x=0 then 0 else x - 1 @R(z1,i21) 2.substraction2: substraction(x,y) = if x < y then 0 ...
66 views

78 views

### Does there exist a valid first-order formula whose Skolemization is satisfiable only with uncomputable functions?

Let $F$ be a valid first-order formula. Then the Skolemization of $F$, let's denote it by $F_S$, is at least satisfiable. Let's say $F_S$ contains function symbols $f_i$ for $1 \leq i \leq n$, for ...
120 views

### $P_1 \vee P_2$ , $Q_1 \vee Q_2$ are semi-decidable predicates and $P_2 = \overline{Q_2}$. What can be said about $P_1 \vee Q_1$? [duplicate]

We've just started studying the decidability notion in our Algorithms class. So far we've only defined it and went through some examples of problems that fit different cases : decidable, semi-...
26 views

### What class of probability distributions do probabilistic turing machines induce?

What class of probability distributions is induced by the class of probabilistic turing machines? Is there a precise characterization?
47 views

### Is this set recursively enumerable/recursive?

I've recently started studying the ideas behind algorithms. That being said, I found myself browsing through different sorts of problems in order to get a better grasp on the subject. Inspired by ...
21 views

### Incomparable hyperdegrees in $\Delta^1_2$, where one of the two is given

In classical recursion theory, given a set $x \le_T 0'$, one can construct a set $y \le_T 0'$ such that $x$ and $y$ are incomparable. Is the following analogous statement in hyperarithmetical theory ...
### $\Pi^1_1$ singletons and $\Delta^1_2$ wellorders on $\omega$ in $L$
I have been trying to show the supremum $\delta^1_2$ of ordinals that are $\Delta^1_2$ wellorders on $\omega$ is exactly equal to the least ordinal $\delta$ such that $L_\delta$ contain all $\Pi^1_1$ ...