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

learn more… | top users | synonyms

-3
votes
1answer
30 views

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

A = {(M) : M is a DTM that rejects}, B = {(M) : M is a DTM that accept } The languages A and B are disjoint, and are both Turing-recognizable. Prove that there does not exist a decidable language C ⊆ ...
0
votes
1answer
35 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
58 views

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

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
23 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
63 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? So the UTM is like a CPU of a computer so any ...
-2
votes
0answers
27 views

Computability theory: language that can be ACCEPTED [closed]

The following is a homework question that has already been due, but I would still need to understand for my tests. I have two languages here and I am trying to figure out if they can be accepted or ...
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
106 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
22 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 ...
13
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 ...
5
votes
1answer
38 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
76 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
70 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
65 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
35 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
44 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 ...
-2
votes
0answers
11 views

Prove the existence of a language L such that L and {0,1}$^*-L$ ($\bar L$) aren't recursively enumerable [duplicate]

Prove the existence of a language L such that L and {0,1}$^*-L$ ($\bar L$) aren't recursively enumerable I know that the existence of something is out of the set RE U CO-RE. With Cantor's ...
-1
votes
1answer
30 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
87 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
459 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 ...
2
votes
0answers
23 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
56 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
117 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
103 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
99 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
119 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
43 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?
8
votes
0answers
60 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
157 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
78 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 ?
2
votes
1answer
68 views

Power of variants of Turing machines

I'm having trouble with this problem as I haven't discovered a good way to determine the power of a Turing machine. I was under the impression that if a Turing machine can perform the same actions ...
2
votes
1answer
49 views

What is a standard way to construct a turing machine for any function to compute

I am new to turing machines, I am having problems with mapping a function to a turing maching that computes that particular function. for example: f(x) = 2x + 3 n>= 0 MIN(x,y) leaves the smallest ...
12
votes
2answers
1k views

In what sense is the Mandelbrot set “computable”?

The Mandelbrot set is a beautiful creature in Mathematics. There are a lot of beautiful images of this set created with high precision, so obviously this set is "computable" in some sense. However, ...
1
vote
1answer
52 views

m-functions in Turing's paper “On Computable Numbers and applications…”

I was reading Alan Turing's paper "On Computable Numbers with an Application to the Entscheidungsproblem". I was reading well until I encountered "4. Abbreviated Tables", page 235-236, where Turing ...
0
votes
1answer
45 views

Prove Undecidability: TM M enters each of its states on Input W?

Consider the following problem: given a Turing Machine $M$ and an input string $w$, does $M$ enter each of its states during its computation on input $w$? How to prove that the problem is ...
1
vote
1answer
24 views

Proving a language to be Recursively Enumerable?

I know to prove a language to be Recursively Enumerable, it is ideal to represent a Turing machine for it. Let L be set of strings which have alphabet {u,d,l,r}, where u is up 1, d is down 1, etc. L ...
1
vote
2answers
47 views

Curry Howard correspondence and Church-Turing thesis

Curry-Howard correspondence states the equivalence between logic/deduction and types/programs. The Church-Turing thesis states the equivalence of some models of computation. Specifically, all ...
3
votes
1answer
24 views

Why is it true that the relation R and its negation are not semi decidable?

An example given for a relation R where its negation and itself are not semi-decidable was: $R(x,y)$ holds iff $y = 0$ then $R_{HALT}(x)$ holds, otherwise $y = 1$ and $R_{HALT}(x)$ does not hold. ...