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

learn more… | top users | synonyms (1)

3
votes
1answer
80 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 ...
0
votes
1answer
106 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 ...
1
vote
1answer
112 views

How to argue that a set is recursive or recursively enumerable?

I have the two sets listed below, and I want to argue whether each of them is recursive, recursively enumerable or neither recursive nor recursively enumerable. the set $A = \{ i | ...
2
votes
2answers
132 views

How to define $f(x) = 2x$ as a recursive and lamba function?

How can I exhibit a recursive function and a $\lambda$-term simulating the function $f : \mathbb{N} \rightarrow \mathbb{N}$, such that $f(x) = 2x$? For $\lambda$ part, I thought to create a mult ...
1
vote
1answer
95 views

A function given a string ( a program) accepts it if the next program which halts does so in an odd number of steps… is it turing computable

A function which given a string returns 1 if the next program halts with an odd number of steps and 0 otherwise. Is this function computable f(s)=1 if w halts in odd number of steps where w>s and ...
4
votes
1answer
34 views

Weak and strong computability of real numbers

Let me adopt the following definitions: A real number $x$ is weakly computable if it satisfies one of equivalent definitions given here. A real number $x$ is strongly computable if the binary ...
0
votes
1answer
65 views

Prove that this function is primitive recursive?

Let $g : \mathbb{N} \rightarrow \mathbb{N}$, $n\mapsto$ the $(n+1)^{th}$ natural number which is not prime. I have to prove that $g$ is a primitive recursive function. My attempt is by minimization ...
0
votes
1answer
45 views

Is Soare still the go-to comprehensive guide of computability, or should I use a different textbook?

So, I was looking up some old threads, and I saw Robert Soare's Recursively Enumerable Sets and Degrees get a lot of Praise. However, I also saw the following textbooks be praised quite a bit: ...
1
vote
0answers
32 views

Undecidability and the representation theory of $K<X,Y>$

The question comes from the problem here: http://mathoverflow.net/questions/73940/are-wild-problems-related-to-undecidable-ones It has already been proven that the representation theory of ...
3
votes
1answer
41 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 $ ...
5
votes
2answers
58 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 ...
1
vote
2answers
39 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?
3
votes
1answer
56 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 ...
4
votes
1answer
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 ...
0
votes
1answer
47 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 ...
1
vote
1answer
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 ...
2
votes
1answer
96 views

Is there a statement which require an infinite computation to check, independent of whether its true or false?

Let P be the statement that a particular equation has no solution in integers , if P is true it might not have a proof so that to verify it one has to check all the (countable infinite) cases. However ...
2
votes
1answer
132 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 ...
4
votes
1answer
83 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, ...
1
vote
1answer
25 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 ...
1
vote
2answers
36 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 ...
0
votes
1answer
36 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: ...
-1
votes
1answer
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 ?
0
votes
1answer
35 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 ...
1
vote
0answers
30 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 ...
0
votes
0answers
44 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 ...
8
votes
1answer
105 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 ...
1
vote
1answer
57 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 ...
0
votes
1answer
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 ...
1
vote
0answers
28 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 ...
1
vote
1answer
82 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 ...
3
votes
0answers
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 ...
0
votes
1answer
19 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.
0
votes
1answer
24 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 ...
3
votes
1answer
44 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? ...
1
vote
0answers
38 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 ...
2
votes
1answer
61 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 ...
3
votes
1answer
92 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 ...
0
votes
1answer
24 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 ...
0
votes
1answer
66 views

Language decidability and Post's theorem

I have the following exercise on decidability: Show that the language $L$ is decidable if and only if there exist decidable languages $A$ and $B$ such that $L=\{x\;|\;(\exists y)[\langle x, ...
0
votes
0answers
27 views

Proving correctness for code computing function.

I was solving an exercise from the book "Complexity, computability and languages" which asks: Write a program that computes $f(x)=1 \iff x$ is even, $f(x)=0\iff x$ is odd. I wrote the following ...
1
vote
2answers
37 views

Can we make witnesses for membership of $\Sigma_2$ sets unique?

A $\Sigma_2$ set $A$ is one for which there is a computable relation $R(x, s, t)$ s.t. $x \in A \iff \exists s \forall t \colon R(x, s, t)$. Can we use $R$ to produce another computable relation $Q$ ...
0
votes
0answers
9 views

Why would proving:$f \in PRC \rightarrow g(y,x_1,…,x_n)=\sum_{t=0}^yf(t,x_1,..,x_n)\in PRC$ by induction be wrong?

Let $PRC$ denote some primitive recursive closed class. Why would proving: $f \in PRC \rightarrow g(y,x_1,...,x_n)=\sum_{t=0}^yf(t,x_1,..,x_n)\in PRC$ by induction be wrong? In the book ...
2
votes
1answer
22 views

$f,g_1,…,g_k$ computable imply $h(x_1,…,x_n)=f(g_1(x_1,…,x_n),…,g_k(x_1,..,x_n))$ computable. Does the converse hold?

In the book "Computability, complexity and languages" by Davis, Sigal and Weyuker, the following $\bf THEOREM$ If $f,g_1,...,g_k$ are computable functions, then ...
4
votes
2answers
77 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 ...
1
vote
0answers
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, ...
0
votes
0answers
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?
2
votes
2answers
43 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 ...
0
votes
0answers
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 ...
3
votes
1answer
80 views

$\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$ ...