Questions related to computability theory, a.k.a. recursion theory

learn more… | top users | synonyms

9
votes
3answers
617 views

undecidable problem and its negation is undecidable

A lot of "famous" undecidable problems are nonetheless at least semidecidable, with their complement being undecidable. One example above all can be the halting problem and its complement. However, ...
0
votes
0answers
18 views

Can we use Rice's theorem to prove that A_TM is undecidable? [duplicate]

I am confused as to whether what constitutes a valid property. My text states that "The domain of property P must be the set of SD languages". Now, $A_{TM} = \{ \langle M,s \rangle \, | \text{ M is ...
1
vote
0answers
60 views

Undecidability of an existential theory

$F[u, u^{-1}]$ is a ring that contains the polynomials in $u$ and $u^{-1}$ with coefficients in the field $F$. Some theorems (from ...
1
vote
1answer
38 views

Collisions in independent hashing

Let $H$ be a $s$-wise independent family of hash functions from $\{1,\ldots,M\}$ to $\{1,\ldots,N\}$. It is easy to bound one collision, but are there good bounds for muliple collision ?
2
votes
3answers
62 views

Reduction from $L_{nonuniversal}$ to $L_{finite}$

As I'm currently preparing for my Algorithms and Complexity exam, I was facing today an other reduction and I'm not quite sure if I solved it correctly. Given are two languages $L_{finite}$ and ...
-3
votes
1answer
42 views

Is $H_0$ reducible to $\overline H_0$?

Be $H_0$ the special halting problem with $$H_0 = \lbrace \langle M \rangle \in \lbrace 0,1 \rbrace^* | \varepsilon \in L(M)\rbrace$$ and $\overline{H_0}$ being its complement. Is $H_0$ reducible to ...
2
votes
0answers
26 views

Undefined behaviour when composing primitive-recursive with $\mu$-recursive functions?

It is quite easy to show that the following two functions are primitive recursive and thus also $\mu$-recursive: $$ifthen(n,a,b) = \begin{cases}a & n > 0 \\ b & else\end{cases} $$ $$ ...
1
vote
0answers
24 views

How does one calculate the block-sensitivity of a function?

I am looking at this paper : http://arxiv.org/pdf/1411.3419v1.pdf But somehow I am not being able to fish out a method to calculate this quantity called the "block-sensitivity". Can someone kindly ...
12
votes
2answers
154 views

When is the concatenation of two regular languages unambiguous?

Given languages $A$ and $B$, let's say that their concatenation $AB$ is unambiguous if for all words $w \in AB$, there is exactly one decomposition $w = ab$ with $a \in A$ and $b \in B$, and ambiguous ...
11
votes
5answers
4k views

Why is a quantum computer not capable of solving more problems than a classical computer?

On the Wikipedia page for quantum algorithm I read that [a]ll problems which can be solved on a quantum computer can be solved on a classical computer. In particular, problems which are ...
-2
votes
1answer
49 views

Two Disjoint Turing-recognizable languages do not have a decidable language

Let languages $A, B$ be defined as $$\begin{align} A &= \{\langle M\rangle\mid M(\langle M\rangle)=reject\}\\ B &= \{\langle M\rangle\mid M(\langle M\rangle)=accept\} \end{align}$$ In other ...
0
votes
1answer
40 views

Showing that the set of DTMs that run forever is not Turing-recognizable

The language A, that is all DTMS that run forever on input. Would this not just be the HALT problem? Therefore no reduction or proof is necessary, other then stating that? ANSWER FOUND: I think i ...
9
votes
5answers
3k views

Could the Halting Problem be “resolved” by escaping to a higher-level description of computation?

I've recently heard an interesting analogy which states that Turing's proof of the undecidability of the halting problem is very similar to Russell's barber paradox. So I got to wonder: ...
-1
votes
2answers
59 views

Is there a computation that takes the same amount of time to run on any computer? [closed]

I'm looking for research that has been done towards finding types of computations that take the same exact amount of time to run, regardless the amount of computing power one has. I've been thinking ...
1
vote
1answer
30 views

Simplest Turing-complete ruleset for Markov algorithm

Is there an example of a particular ruleset for a Markov algorithm that is Turing-complete? If so, what is the simplest example of such a ruleset?
-4
votes
1answer
73 views

What is a Universal Turing machine? [closed]

What is a Universal Turing machine and can it really operate like any possible computable algorithm that is represented as a specific Turing machine? I read previously a UTM might work if any turing ...
2
votes
0answers
20 views

Computational models - proving language is decidable [duplicate]

I tried to prove that the following language is recursive/decidable/in R: for $\Sigma=\{0,1\}$, $k$ a positive integer: $$ L_k= H_\text{TM,epsilon}\cap \Sigma^k $$ where $H_\text{TM,epsilon}=\{\langle ...
7
votes
3answers
114 views

Constructive proof of decidability of finite Halting-problem-style set that does not use table lookup

I tried to prove that the following language is recursive: for $\Sigma=\{0,1\}$, $k$ a positive integer: $$ L_k= H_{\mathrm{TM},\varepsilon}\cap \Sigma^k $$ where ...
0
votes
0answers
24 views

Proving that $L=\{ \langle M \rangle \colon L(M)=L(M)^R \}$ is undecidable [duplicate]

I'm trying to show that $L=\{ \langle M \rangle \colon L(M)=L(M)^R\}$ is undecidable, but I don't even know where to begin. Google wasn't much of a help, maybe because it's hard describing the ...
14
votes
5answers
2k views

Why can functional languages be defined as Turing complete?

Perhaps my limited understanding of the subject is incorrect, but this is what I understand so far: Functional programming is based off of Lambda Calculus, formulated by Alonzo Church. Imperative ...
6
votes
2answers
71 views

How can a cyclic tag system halt with an output?

For example, we can say we have a abstract program that, given a finite binary string as input, removes all of the zeros (i.e. 0010001101011 evaluates to 111111), which is definitely a ...
2
votes
2answers
80 views

Universal binary rewriting system

What is the simplest example of a rewriting system from binary strings to binary strings $$f:\Sigma^*\rightarrow\Sigma^*\qquad\Sigma=\{0,1\}$$ that can perform universal computation? Binary string ...
-4
votes
1answer
74 views

Set of Turing machines that halt after exactly 14 steps [closed]

Let $M_i$ be the Turing machine with Gödel number $i$. Let $$A = \{i \mid M_i \text{ with input \(x\) halts after exactly 14 steps}\}$$ Is the set $A$ recursive?
1
vote
1answer
66 views

Checking acceptance of a word vs finding an accepted word

We know that checking whether some word w is accepted by a turing machine TM is undecidable. But what about the problem of finding one accepting word of a TM? Are these two problems related in some ...
3
votes
1answer
41 views

Proving that if $L=\{ a^n b^n c^n \colon n\ge 0 \}$ than $L\notin CFL$ [closed]

I'm going over "Introduction to the Theory of Computation" by Michael Sipser in which there's an example of using the pumping lemma for CFLs to prove that $L=\{ a^n b^n c^n \colon n\ge 0 \}$ is not a ...
-1
votes
1answer
49 views

Why decision problem definition ignores Gödel incompleteness theorem?

The following question assume that the decision problem definition (syntactic) has been written (and could be changed if it isn't able) to catch a concept (meaning, semantic) which has both nice ...
3
votes
1answer
55 views

Symmetric Difference of Turing Recognizable and Finite Languages

Let A be a Turing Recognizable Language and B a finite Language. I want to prove that their symmetric difference is Turing Recognizable. My reasoning: B is finite, therefore the finite number of ...
-1
votes
1answer
31 views

Prove L and {0,1}*-L are recursively enumerable [closed]

Exercise ask : Prove which a binary language L is recursive if and only if both L and {0, 1}* - L are recursively enumerable. Now I try to give a solution: Suppose that L is recursively ...
0
votes
0answers
39 views

Which of the two properties isn't satisfied?

Show that the following sequence of function $\Phi_n$ is not a measure of complexity: $\Phi_n(x)=\left\{\begin{matrix} \text{ nr of commands } m \text{ that TM } T_n \text{ executes with ...
6
votes
4answers
88 views

A metaphor for recursive enumerability

In his commentary on a case involving pornography in 1964, U.S. Supreme Court Justice Potter Stewart sidestepped the question of defining what it meant for a work to be pornographic, but then said "I ...
15
votes
6answers
471 views

What exactly is computation?

I know what computation is in some vague sense (it is the thing computers do), but I would like a more rigorous definition. Dictionary.com's definitions of ...
0
votes
2answers
27 views

Constructible enumerable set

We suppose that the sets $S_1$ and $S_2$ are constructible enumerable, that means that there is an algorithm that enumerates them. Show that the sets $S_1 \cup S_2$ and $S_1 \times S_2$ are also ...
3
votes
0answers
29 views

A syntactic property of computing systems: is non-coding DNA universal?

One of the surprising aspect of the genome for lay-people is that it contains important non-coding DNA parts, which does not mean that they are all useless. I never paid so much attention to the fact, ...
0
votes
1answer
33 views

Proving that a set of grammars for a given finite language is decidable [duplicate]

Let the language $$L = \left\{ \langle G \rangle \ |\ L(G) = \{1,\ldots , 1000\}, \text{ G is a CFG }\right\}$$ Prove that $L \in R$. Well, I think that for a start we need to check whether or ...
2
votes
1answer
126 views

Show that the set of all TMs that move only to the right and loop for some input is decidable

I am trying to prove that $\qquad L=\{\langle M\rangle \mid M \text{ is a TM }, \exists w. \text{ in } M(w) \text{ the head moves only right and } M(w)\!\uparrow \}$ is decidable. I thought about ...
-1
votes
1answer
35 views

Why is it true that $NP \ne coNP \implies X = \emptyset$?

Let the class of languages $$X = \{ L \ | \ L\in NPC \land L\in coNPC\}$$ Why is it true that $NP \ne coNP \implies X = \emptyset$?
1
vote
2answers
118 views

Is an infinite language of halting TM is in $RE$? in $RE \setminus R$?

Let an infinite language, $L$, which contains only TM which halt for every input (meaning, decides some language). Is $L$ in $R$ ? in $RE \setminus R$ ? I've understood that the answer is: it ...
0
votes
0answers
29 views

mapping reduction for every recursive language [duplicate]

how do I prove that for every 2 languages $A,B\in R$ where $A,B \notin \{ \emptyset , \Sigma^* \}$ I can do a reduction $A \leq_m B$? [EDIT] My try: $A$ is decidable therefore it has a turing ...
-2
votes
1answer
36 views

Prove/ Disprove: For every nontrivial $A,B \in R (RE)$, $A\le_m B$ [closed]

Prove/ Disprove: For every nontrivial $A,B\in R$, $A\le_m B$ For every nontrivial $A,B\in RE$, $A\le_m B$ trivial set is the empty-set or $\Sigma^*$. So basically the ...
0
votes
0answers
106 views

What is the limit for Turing machines with 2 states and 3 symbols that halt?

I read here that a proof has been offered that a Turing Machine with 2 states and 3 symbols can be universal (in that it is capable of arbitrary finite computations). Even if this proof is accepted, ...
0
votes
0answers
30 views

if P=NP then $L\leq L'$ for all languages [duplicate]

How can I prove that if P=NP then for each non-trivial language $L,L'\in NP$ there exists a polynomial reduction $L\leq L'$?
1
vote
1answer
103 views

A and B are Turing recognizable, is A - B Turing recognizable?

If A and B are Turing recognizable, is A - B Turing recognizable? I think that A - B would be Turing recognizable because they're both in the space of Turing recognizability. For example, if A is ...
7
votes
1answer
125 views

Is the unsolvability of the N-Body Problem equivalent to the Halting Problem

There is no general analytic solution to the n-body problem that can produce an analytic function which can be used to give an n-body system's state at arbitrary time t with exact precision. However, ...
0
votes
1answer
44 views

Why is testing if x > y primitive recursive?

$f(x,y)= 0$ if $x>y$ and $1$ otherwise. How can prove formally that this function is primitive recursive?
9
votes
0answers
68 views

Machines for context-free languages which gain no extra power from nondeterminism

When considering machine models of computation, the Chomsky hierarchy is normally characterised by (in order), finite automata, push-down automata, linear bound automata and Turing Machines. For the ...
0
votes
2answers
89 views

Is the language $\{f(x)\mid \mbox{$x$ is the code of a machine accepting $f(x)$}\}$ recursively enumerable and undecidable?

This is text of an exercise I am working on: Given a binary encoding scheme for the set of the deterministic Turing machines with alphabet $\{0,1\}$ and a bijective and computable function $f: ...
1
vote
0answers
23 views

Proving that pairs of words in resp. not in a TMs language are neither semi- nor co-semi-decidable [closed]

I have a homework assignment in which I am required to determine if $$L = \{ \langle M,x,y \rangle : x\in L(M),y\notin L(M) \}$$ is in $$R,RE-R,coRE-R \text{ or } \overline{RE \cup coRE}$$ Now, my ...
6
votes
4answers
169 views

Undecidable problems limit physical theories

Does the existence of undecidable problems immediately imply the non-predictability of physical systems? Let us consider the halting problem, first we construct a physical UTM, say using the usual ...
19
votes
7answers
2k views

Is there a more intuitive proof of the halting problem's undecidability than diagonalization?

I understand the proof of the undecidability of the halting problem (given for example in Papadimitriou's textbook), based on diagonalization. While the proof is convincing (I understand each step of ...
-1
votes
1answer
80 views

Does every infinite recursive language contain an infinite regular subset? [duplicate]

My intuition is telling me that this is not the case. But I am having trouble formulating a proof for this.How do I prove it ?