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)

-1
votes
1answer
61 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
29 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
40 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
96 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
47 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
49 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
26 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
80 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
16 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
40 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
36 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
55 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
85 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
23 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
65 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
25 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
36 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
8 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
76 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
40 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
20 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
75 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$ ...
1
vote
0answers
27 views

Having trouble with the basic interpretation of “s-m-n theorem”

enter image description here This is the definition, the issue is, I still don't understand the basics. Here is my interpretation. If we have a computable function f(x,y), we can assign all the ...
2
votes
1answer
54 views

Recursive function $f$ with $\operatorname{range}(f) = \{x\mid \phi_{x}\text{ is total}\}$ [closed]

I don't understand how the proof for this exercise (and this kind of exercises in general) holds: There is no recursive function $f$ with $\operatorname{range}(f) = \{x\mid \phi_{x}\text{ is ...
2
votes
3answers
76 views

Why are all finite sets recursive?

Obviously a finite set for which the members are explicitly given or for which a computable rule is available will be recursive. (By which I mean its characteristic function is computable.) However, ...
0
votes
0answers
94 views

Language decidable separates two disjoint co-Turing recognizable languages

Hello this is the problem: Let A and B be two disjoint languages. Say that language C separates A and B if A in C and B in (not C). Show that any two disjoint co-Turing-recognizable languages are ...
0
votes
1answer
34 views

What does it mean to prove a problem cannot be solved by a Turing machine?

You sometimes see claims that no Turing machine exists which solves a particular problem, for example, no Turing machine exists which, given an arithmetic statement, outputs correctly either "true" or ...
2
votes
1answer
51 views

Are there decidable problems which aren't in $NP$?

I'm currently attending a course introducing the basic notions of algorithms, complexity, decidability etc. My question is: Is there a decidable problem $A$ which isn't in $NP$, i.e. it is always ...
2
votes
1answer
65 views

Corollary of Kleene's recursion theorem - can we find a constructive proof?

It is not a homework assignment, rather it is a question arising from teaching myself. In a lecture note by Weber, following statement gives as a corollary of Kleene's recursion theorem: For ...
1
vote
0answers
48 views

How to prove a programming language is not Turing complete?

How does one prove that a programming language is not Turing complete? I know one may attempt to show that every program that could be written in the programming language in question is primitive ...
1
vote
0answers
16 views

A preordered set related to realisability logic

Let $\Lambda$ be any partial combinatory algebra. For each set $X$, define a binary relation on $\mathscr{P} (\Lambda)^X$ as follows: Given $P, Q : X \to \mathscr{P} (\Lambda)$, $P \le_X Q$ iff ...
1
vote
2answers
30 views

If a c.e. set $X$ is such that every $\Sigma^0_2$ set is c.e. in $X$, then $X \equiv 0'$

Is it true that if a c.e. set $X$ (of naturals) is such that every $\Sigma^0_2$ set $Y$ is c.e. in $X$, then $X \equiv 0'$? An obvious and naive trial to prove this would be to take $Y := 0''$. ...
3
votes
2answers
97 views

Proofs about theorem-provers in ZFC, in ZFC

Is the following statement provable in ZFC for some $A$: "$A$ is an algorithm which, when given as input a proposition $p$ in the language of ZFC, outputs 'yes' only if $p$ is provable in ZFC, 'no' ...
1
vote
1answer
20 views

Is there a typical amount of clauses (in a 3CNF SAT expression)? Do SAT solvers regularlary solve expressions (or attempt to) with many?

I'm curious as to in what settings we would be interested in finding out whether a boolean expression in 3CNF with a large number of clauses is satisfiable (I''m not sure how "large number" is defined ...
1
vote
1answer
12 views

Does any non-admissible numbering form a PCA?

Given a numbering $\varphi_0, \varphi_1, \dotsc$ of the unary partial recursive functions, define a PAS as $\mathbb N$ with application $x \cdot y \simeq \varphi_x(y)$. If the numbering is admissible ...
3
votes
1answer
73 views

Markov's paper on insolubility of the homeorphy problem

I am looking for an English translation of Markov's 1958 paper, On insolubility of the homeorphy problem, which I remember coming across on a website for a computational topology course (taught by ...
2
votes
1answer
85 views

Is there a way to decide whether a differential equation is solvable or not?

Martin Davis, Yuri Matiyasevich, Hilary Putnam and Julia Robinson had negatively settled Hilbert 10th problem, I wonder if there is an analog result to the differential equations ?
2
votes
1answer
75 views

Parity of TREE(3)?

The number TREE(3) is somewhat famous for being incomprehensible big. But since it's just a finite number it must have a parity. Is the parity of TREE(3) known?
1
vote
1answer
31 views

Recursive languages , please check whether my explain is correct?

Nobody knows yet if $P=NP$. Consider the language $L$ defined as follows. $$L = \begin{cases} (0+1)^* & \text{if } P = NP \\ \phi & \text{otherwise} \end{cases}$$ Which of the following ...
6
votes
0answers
163 views

Anti-random reals

EDIT: This has now been crossposted at MO: http://mathoverflow.net/questions/219366/antirandom-reals. This is partially motivated by my question at mathoverflow: ...
0
votes
1answer
72 views

enumerability exercise in boolos book

problem 2.2 of Computability and Logic written by Boolos(p.20, fifth edition) Show that if for some or all of the finite strings from a given finite or enumerable alphabet we associate to the string ...
0
votes
1answer
46 views

Proving finite-automata transition function for string concatenation

I'm having a few problems with this proof and I'm not sure where to start. In our class, a Deterministic Finite Automata, or DFA, is defined as a 5-tuple $$M = (Q,\Sigma,\delta, q_0, F) $$ Where ...
1
vote
1answer
33 views

Let $G(x,y)=2^x(2y+1)-1$ and show that $G$ is computable

Show that $G$ is a computable bijection and that the functions $G(G_1(z))$,$G_2(z))=z$ for all $z$ is computable. To show that it is computable, do we show that the above function $G$ is primitive ...
4
votes
0answers
71 views

Show undecidability by reducing from Hilbert's $10^{th}$ problem

To show that the existential theory of $\mathbb{Z}$ in the language $\{0, 1; +, \mid , \mid_p\}$ (where $x \mid_p y \Leftrightarrow \exists r \in \mathbb{N} : y=\pm xp^r$) is undecidable we have to ...