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

learn more… | top users | synonyms (1)

2
votes
3answers
83 views

Showing that a certain recursive set cannot exist?

I'm having a lot of trouble with problem 17.2 of Computability and Logic (Boolos, Burgess, Jeffrey). Here's the problem: Let $T$ be a consistent, axiomatizable theory (in the language of ...
4
votes
1answer
78 views

Turing Machine Problem

We know, A Turing machine is a hypothetical device that manipulates symbols on a strip of tape according to a table of rules I Draw a TM for input $x=(0+1)^*$ i want to implement ...
2
votes
1answer
152 views

Turing machines that compute $\pi$

For each $K > 0$ there is a brut force Turing machine $\pi_K$ that "computes" the first $K$ digits of $\pi$ starting on the blank tape (all $b$s) with $K+1$ states $S \in \mathsf{S} = ...
0
votes
0answers
47 views

Arithmetic Turing machines

Consider the family $T_{1}$ of Turing machines with two tape symbols $b,1$ ($b$ the blank symbol). The family $T_{1}$ is Turing complete. Identify the tape with $\mathbb{Z}$ and let $0\in \mathbb{Z}$ ...
0
votes
1answer
31 views

infinitely long input for a turing machine

I have a question about Turing machines. Is it allowed to give them infinitely long input? Can I give a Turing machine for example all of natural numbers as input?
1
vote
0answers
36 views

Proof that Finite Turing Machine is reducible to Regular Turing Machine

I know that Finite Turing Machine and Regular Turing Machine are undecidable through Rice's theorem, but I may find a reduction among them? Finite TM = {< M > | L(M) is finite on {a}} Regular TM ...
3
votes
2answers
37 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
31 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
67 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
50 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
50 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 ...
0
votes
1answer
64 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
24 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 ...
-1
votes
1answer
38 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
140 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
193 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
21 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
19 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
32 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
95 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 ...
4
votes
0answers
50 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
36 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
85 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
75 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
70 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
71 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
37 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 ...
2
votes
1answer
91 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
80 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 ...
0
votes
1answer
72 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 ...
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
47 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
41 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
38 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
58 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
36 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
75 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 ...
3
votes
1answer
73 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
71 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 ...
1
vote
0answers
55 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
110 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: ...
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
97 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
87 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
58 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
53 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
91 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?
0
votes
3answers
32 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?
2
votes
0answers
22 views

Computable models of ($\omega$, <) without computable isomorphism

I read somewhere that "it is easy" to construct a computable presentation for the model ($\omega$, <) so that any computable isomorphism between this construction and the usual presentation of ...
1
vote
1answer
31 views

What techniques are there to search for first order sentence equivalence?

Suppose we have a first order sentences $\phi$, $\psi$, and $\chi$ such that: $\phi$ $\longleftrightarrow$ ($\psi$ $\land$ $\chi$) And $\phi$ and $\chi$ are known or fixed. How can we search for a ...