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
2answers
21 views

Number of $1$s in the binary representation of $n$

Trying to define the function $b(n)$ which counts the number of $1$s in the binary representation of $n$ arithmetically I came up with the following definition: $$b(n)=m :\equiv (\exists k_1\dots ...
0
votes
1answer
20 views

TOTAL is not Recursively Enumerable

$\overline{HALT}=$ { (M, w) : M does not halt on w } $TOTAL=$ { M : M halts on every input } The following is the proof from Hopcoft that TOTAL is not R.E. Let R(x) be the following machine: ...
1
vote
1answer
59 views

Countable Set & Formal Grammar

We know set A is countable if A is finite or in a one-to-one mapping to natural numbers. I try to summarize my though. I think the following proposition is true. suppose $\Sigma$ is arbitrary ...
2
votes
1answer
39 views

Binary representation of real numbers without dots

How can I represent a real number using only 0's and 1's? I do not want to use any extra symbol like '.' to separate the integer part and the mantissa.
1
vote
1answer
21 views

In general, are subsets of recursively enumerable sets recursive sets?

I recently became interested in the solution to Hilbert's tenth problem, in reading about the succession of results that lead up to the proof I came across the notion of recursive sets and ...
2
votes
0answers
22 views

Strange Turing Machine Definition [closed]

i prepare for Autotmata Course Final Exam. in one of lecture, our professor draw this Turing Machine, and wrote DELTA is Neutral element of TM. it'w wrote: Language of this TM is: {$W \in ...
0
votes
1answer
15 views

What's time complexity of algorithm for “Word Break”?

Word Break(Dynamic Programming) Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible ...
0
votes
0answers
20 views

Generalization of standard technique for proving that an undecidable language is unrecognizable

Suppose $L = \{P:P(x) \; outputs \; x^2 \;for\; all\; x\}$ Then $\bar L = \{P: P(x)\; does\; not\; output\; x^2 for\; all\; x \}$. By Rice's Theorem or by reduction from the Halting Problem, let's say ...
-2
votes
0answers
37 views

Pumping Lemma & Regular Language

For each regular language L, we have an integer k such that: ...
-1
votes
1answer
35 views

$L \in RE$ Question in Computation [closed]

Let L be a language. Suppose a TM exists that halts on all words in L. Which of the following statements is true? a) if L is r.e we have such TM. b) if L is r.e and complement of L is r.e then we ...
4
votes
2answers
115 views

What if a conjecture were provably unprovable?

Suppose we found a proof that "The Twin Prime Conjecture cannot be proven", without any conclusion as to the conjecture itself being true or false. Is it then possible for the conjecture to be true? ...
9
votes
2answers
169 views

The mother of all undecidable problems

It is usual to show that a problem P is undecidable by showing that the halting problem reduces to P. Is it the case that the halting problem is the mother of all undecidable problems in the sense ...
0
votes
1answer
15 views

Algorithm that takes input desc. of two PDAs and outputs intersection of langs. recognized by two PDAs

Does there exist an algorithm which takes as input the descriptions of two pushdown automata, $P1$ and $P2$, and prints the description of another pushdown automaton which recognizes the intersection ...
0
votes
1answer
17 views

Deciding TM which fails to halt whenever the length of its input string is a prime number

I have the following Statement: "A TM called $A$ which fails to halt (i.e runs forever) whenever the length of its input string is a prime number, and eventually halts for all other input strings" ...
-1
votes
1answer
21 views

disproving union of infinitely many regular languages

I want to disprove the following statement: "if $L$ is the union of infinitely many regular languages, then $L$ is guaranteed to be a regular language." I don't know where to start. Any hint will be ...
4
votes
0answers
86 views

Is it decidable whether the iterates of a polynomial map are bounded?

Let $f:\mathbb{Q}^n\to \mathbb{Q}^n$ be a polynomial map with rational coefficients. Let $p\in \mathbb{Q}^n$. Is there a known algorithm that given this data determines whether or not the iterates ...
0
votes
0answers
42 views

predicate logic with assumption NP $\neq$ CO-NP?

Anyone could describe why: Set of All Tautology in propositional logic with assumption NP $\neq$ CO-NP is CO-NP Complete. Thanks. I ask it here before: Is the language of tautologies NP-complete? ...
0
votes
1answer
25 views

Computable Function and Predicate Question

I See on Our Lecture note on Theory of Computation Course that: .... The basic characteristic of a computable function is that there must be a finite procedure (an algorithm) telling how to compute ...
6
votes
1answer
76 views

Who first discovered that some R.E. sets are not recursive?

Who first discovered that some recursively enumerable sets are not recursive, or equivalently that some semidecidable sets are undecidable? And in what context? Was the earliest formulation of this ...
-2
votes
1answer
73 views

D={ $ deg_T (A) | A \subseteq N$} Problem [closed]

Dear friends I wanted to ask the question that already asked 2 times but it's on-hold and after few days deleted, but I didn't get any answer. I try to solve it but confused. I don't know anything and ...
1
vote
1answer
61 views

set theory, Incompleteness and axiomatic systems

Is the number of theorems that can be proved (decidable) within a certain set of axioms (for instance ZFC) is finite or infinite ? in other words, are we going to fully exhaust that set of axioms ...
1
vote
1answer
47 views

Is the given Language decidable or recognizable?

Let M be a machine that takes a natural number as input and outputs a natural number. Let L = $\{M:\;M(n)\;outputs\;a\;prime\;greater\;than\;n\;for\;every\;n\}$ Is L decidable? Is L recognizable? ...
2
votes
0answers
36 views

Decidability of a language

Let $C$ be a conjecture about natural numbers. Let $$S = \{n\in N: n > m \text{ where $m$ is the first number found for which $C$ is false} \} $$ Is $S$ decidable? If $C$ is true for all ...
0
votes
1answer
75 views

Many to one Reducible & Polynomial time

we know that If $A \le_p B$, then $A$ can be reduced to $B$ in polynomial time. we know that If $A \le_m B$, then $A$ is many to one reduction to $B$ . can we deduce that: if $A \le_m B$ then $A ...
0
votes
1answer
75 views

Why is $x\mapsto x$-th prime number a partial recursive function?

I think that partial recursive functions correspond to all computable functions. Thus, if we can write a computer program to represent a function, the function is partial recursive. In computability ...
-1
votes
1answer
64 views

Undecidability of First Order Logic [closed]

friends! I read in Ebraham's Outline of Logic that first order logic is undecidable because it lacks an algorithmic procedure which reliably detects invalidity in every case. It is undecidable ...
-1
votes
1answer
69 views

The range of an increasing computable function relation is recursive [closed]

I read this post: A is recursive iff A is the range of an increasing function which is recursive, and also this tutorial on recursion theory. In the latter, I saw the following sentence: $A$ is ...
0
votes
0answers
140 views

range of one increasing computation function?

We know that that the range of any recursive partial function is recursively enumerable. Also we know the fact: Set A is recursive if and only if it is range of some increasing section partial ...
0
votes
1answer
40 views

Problems On Many-one Reducible [closed]

In computability theory and computational complexity theory, a many-one reduction is a reduction which converts instances of one decision problem into instances of a second decision problem. ...
-1
votes
1answer
60 views

Recursively enumerable language [closed]

In mathematics, logic and computer science, a formal language is called recursively enumerable (also recognizable, partially decidable, semidecidable or Turing-acceptable) if it is a recursively ...
-1
votes
1answer
35 views

Set of Logical Result Problem [closed]

If we have a set of predicate formulas $A$, and there is an algorithm such that for every predicate formula $X$, (with input $X$), output YES iff $X \in A$. My question is about set of logical result ...
1
vote
0answers
34 views

Is a set $\{ e \in \mathbb{N} | \#\{x \in \mathbb{N} | \phi_e(x) \downarrow \} = \#\mathbb{N}\}$ computable?

Denote every partial computable function $f$ with its Godel number $e \in \mathbb{N}$ by $\phi_e$. Then let the halting set of $\phi_e$ be $W_e=\{x \in \mathbb{N} | \phi_e(x) \downarrow \}$ where ...
1
vote
2answers
57 views

How many recursively definable groups are there on $\mathbb{N}$?

How many non-isomorphic, (non-free), non-trivial, recursively definable groups are there on $\mathbb{N}$? I know we can at least get 1. Let $F:\mathbb{N} \to \mathbb{Z}$ be the "natural bijection". By ...
2
votes
1answer
33 views

Primitive-recursive functions and polynomial equations

I am looking for examples of primitive-recursive functions $f:\mathbb{N}\rightarrow\mathbb{N}$ that can not be written as a pair of polynomials, i.e. $$f(n) = m \Leftrightarrow P(n,m) = Q(n,m)$$ ...
4
votes
2answers
72 views

Uncomputability of subset relation

I suppose this obvious question should already be answered in plenty of places, but for some reasons I cannot find a proof of this anywhere. Prove or disprove that their exist a set $X$ that is ...
2
votes
1answer
58 views

Bijection between computable reals and rationals?

This wikipedia article http://en.m.wikipedia.org/wiki/Computable_number#Properties suggests that there is such a bijection. How does it look like? And how to map computable transcedentals like pi to ...
1
vote
1answer
58 views

Is there a more general proof for the halting problem?

Note:If this question is better suited for a different site, please tell me in the comments. Summary:Is there a proof for the impossibility of the halting problem that doesn't involve calling it on ...
-4
votes
1answer
157 views

Primitive Recursive Predicate Problem [closed]

i get trouble with 2011 midterm exam question. if P(x) and Q(x) be a primitive recursive predicate. which of the following is not a primitive recursive? anyone could describe it for me? 1) $P(x) ...
0
votes
1answer
70 views

$\{x: 2x ∈ M\}$ is R.E Set [closed]

In computability theory, traditionally called recursion theory, a set $S$ of natural numbers is called recursively enumerable, computably enumerable, semidecidable, provable or Turing-recognizable if: ...
1
vote
0answers
48 views

Is this proof for the undecidability of $\beta$-normalisation in $\lambda$-calculus valid?

The proofs I have so far seen for the undecidability of $\beta$-normalisation all make use of Gödel numbering in order to first prove the more general Scott-Curry theorem. As an exercise, I have tried ...
-1
votes
1answer
106 views

Many-one Reducibility Understanding Problem [closed]

We know for every set $B$, that be r.e have: $$B\leq_mK$$ (The set $B$ is many-one reducible, or m-reducible, to the set $K$) we know $K$ is r.e and define: $$K=\{ e:e\in W_e\}$$ my challenge is: ...
-2
votes
1answer
78 views

Computation & R.E Set Problem [closed]

i ran into a old-midterm question recently, without any definition and tutorial Suppose A is a subset of Natural Numbers that includes all numbers except some finite numbers. why A ...
1
vote
1answer
74 views

Big Questions in First Order Logic

if $\Sigma$ is a r.e set (half decidable) of sentence in first order logic, the set of logical result of $\Sigma$ is Recursively Axiomatizable. why this is false? or maybe it's true? ...
2
votes
1answer
87 views

Is it decidable: is there an input for which turing machine will move its head left?

$L=\{\langle M \rangle | M $is a Turing machine and $\exists$ input $x$ such that in $M(x)$ running $M$ moves its head left at least once $\}$ Is $L$ decidable?
3
votes
2answers
85 views

Distinguishing sets according to more fine-grained notions than cardinality.

I'm interested in distinguishing sets according to more fine-grained notions than cardinality. Now I don't know a thing about computability theory, but it seems to me that considering sets up to ...
-1
votes
1answer
55 views

Computable Set & Function

we know that i read this sentence are true? can anyone say an example for following sentence? there are a non computable set A such that
0
votes
1answer
52 views

Logic & Computability Problem

i read this sentence in one exam that be false. anyone could say why? if predicate H(x) become false when a program with code r(x) halt on input l(x), then H be a computable predicate.
0
votes
1answer
87 views

Turing & Computability & Computation

We know if we have: we can show (T=t= Turin Redu.) but i have no idea why this relation be correct? any idea?
2
votes
0answers
50 views

Big Challenge in TM & R.E Set [closed]

we know that Halting problem {(M.w) | M halts on input w} is r.e but not recursive. i see the following sentence in one book. "the set of {(M.w) | M halts on input w and M is a TM}} is not r.e" ...
0
votes
3answers
26 views

Recursive Set in Partial Computable Function Problem

Suppose $A, B, C$ are disjoint set such as shown on this figure. $f_1(x), f_2(x), f_3(x)$ is partially computable function. why $A,B,C$ is recursive set?