Questions about problems which cannot be solved by any Turing machine.

learn more… | top users | synonyms

3
votes
1answer
28 views

Deciding the set of all Turing machines that halt in at most $k|x|$ steps $\forall x \in \Sigma^*$

Let $L = \{ <M> | M$ halts on every input $x$ in at most $200 * |x|$ steps $\}$. Is $L$ decidable? Recognizable? Given that membership in $L$ asserts something about $M$'s behavior on an ...
1
vote
1answer
21 views

How do you prove that this TM decides a language that is undecidable? [on hold]

In Sipser's Introduction to the Theory of Computation, there is an exercise that asks to prove $T$ decides $A_{TM}$, which is the language $$A_{TM} = \{ \langle M,w \rangle | M \text{ is a TM and $w ...
1
vote
1answer
28 views

Proof that $A_{DFA}$ is decidable in Sipser

It seems like the proof that $A_{DFA}$ is decidable in Sipser (2nd ed.) assumes the computation will halt... and hence only really proves that $A_{DFA}$ is recognizable. The language $A_{DFA}$ is ...
4
votes
2answers
164 views

Why is the halting problem decidable for LBA?

I have read in Wikipedia and some other texts that The halting problem is [...] decidable for linear bounded automata (LBAs) [and] deterministic machines with finite memory. But earlier it is ...
0
votes
1answer
62 views

how do I find a undecidable subset of a set that's decidable? [closed]

Given that Let S = {a | |a| is odd}. I know that since S is decidable, but does there exist a subset within S that is undecidable?
0
votes
0answers
9 views

two undecidable languages with a decidable union/intersection? [duplicate]

does there exist two undecidable languages such that their union is decidable? what about a decidable intersection? One thing that I've been trying to figure out is if J and K are both undecidable ...
4
votes
2answers
466 views

Sandwiching Languages

I am studying for my algorithms final and came across the following problem: Find three languages $L_1 \subset L_2 \subset L_3$ over the same alphabet such that $L_2 \in P$ and $L_1,L_3$ are ...
4
votes
2answers
120 views

Is this language depending on P = NP recursive?

Nobody yet knows if ${\sf P}={\sf NP}$. Let us consider the following language $$L = \begin{cases} (0+1)^* & \text{ if ${\sf P}$ = ${\sf NP}$} \\ \emptyset &\text{ otherwise}. \end{cases}$$ ...
0
votes
1answer
41 views

Palindromes and linear grammars

Given a linear grammar G, is it possible to determine if L(G) contains a palindrome?
2
votes
1answer
48 views

Undecidability and Countability

This question is prompted by Undecidable unary languages (also known as Tally languages) How does the countability of a language imply (un)decidability?
2
votes
2answers
85 views

Is equivalence of CFGs decidable for finite sets of grammars?

Is there a way to show that for all finite sets $S$ of context free grammars, there exists a Turing Machine $M$ such that for all grammars $G_1, G_2 \in S$, we have that $M(G1,G2)$ terminates and ...
1
vote
1answer
85 views

Reduction to complement of Accept Problem

I am reducing a given Turing Machine to the complement of the known undecidable problem, $$ Complement(A_{TM}) = \{ \langle M,w \rangle \mid M \text{ is TM}, w \not\in L(M) \}$$ To this Turing ...
1
vote
3answers
86 views

Determining if a context-free grammar produces even-length strings [closed]

Given a context-free grammar, is there an algorithm to determine if the CFG will ever produce an even length string? Or is this undecidable?
1
vote
1answer
43 views

Decidability of an regular expression

I have this question about if the decidability of an regular expression and would appreciate if someone can check my answer and see if it makes sense, and if not, what is missing. Be A = {(R)|R it ...
4
votes
1answer
58 views

Is it possible to prove EQTM is undecidable by the Rice theorem?

Given the problem $EQ_{TM} = \{ \langle M_1, M_2\rangle \mid M_1 \text{ and } M_2 \text{ are } TM, L_{M_1} = L_{M_2}\}$, is it possible to prove that this is undecidable by using (a variant of) Rice ...
0
votes
1answer
18 views

Decidability of fullness of intersection of a CSL with a regular language

Let $L_r$ be a regular language with alphabet $\Sigma$ and $L_{\text{csl}}$ be a context sensitive language. Are any of the following questions decidable? $L_r \cap L_\text{csl} \stackrel{?}{=} L_r$ ...
1
vote
1answer
70 views

Understanding a proof for the existance of a non-computable function

For school, we have a proof that some functions are not Turing computable. The example is: $$ G(k) = \begin{cases} f_k(k) + 1 & \text{ if $f_k(k)$ is defined}, \\ 1 & \text{ ...
1
vote
3answers
132 views

Is the image of a total, non-decreasing function decidable?

This is an exercise I've been struggling with for a while: Let $g : \mathbb{N} \to \mathbb{N}$ be a total, non-decreasing function, i.e. $\forall x > y.\ g(x) \geq g(y)$. Is the image $I_g$ of ...
0
votes
1answer
62 views

Can a semi-decidable problem be also decidable?

As far as I understand, a semi-decidable (recursively enumerable) problem could be: decidable (recursive) or undecidable (nonrecursively enumerable) ...
0
votes
1answer
32 views

Turing Machine 'marking' specific portion of encoding

Given a turing machine $T$ that receives an encoding of another turing machine and a word $<M><w>$, can $T$ 'run' through the encoding and 'mark' specific transitions/states? For example, ...
4
votes
1answer
150 views

Why is deciding regularity of a context-free language undecidable?

As I have studied, deciding regularity of context-free languages is undecidable. However, we can test for regularity using the Myhill–Nerode theorem which provides a necessary and sufficient ...
2
votes
2answers
532 views

Undecidable unary languages (also known as Tally languages)

An exercise that was in a past session is the following: Prove that there exists an undecidable subset of $\{1\}^*$ This exercise looks very strange to me, because I think that all subsets are ...
0
votes
0answers
73 views

Intersection between context-free and context-sensitive language decidability

I'm trying to find a formal proof of the following fact: Given a context-free language $L_1$ and a context-sensitive language $L_2$, it is NOT decidable if their intersection is empty ($L_1 \cap ...
3
votes
1answer
40 views

Question about the undecidability of $A_{TM}$

You probably know this one (or at least a version of it). Let $P$ be a program code, and $w$ be an input string. Define $A_{TM}=\left\{(P,w)| P(w)=1\right\}$. Meaning: $A_{TM}$ is the set of all ...
0
votes
2answers
62 views

Mapping reduction to show NeverHalt is undecidable

I need help with showing that $$NeverHalt_{TM} = \{\langle M\rangle \mid \text{$M$ is a TM which runs forever on every input $w$}\}$$ is undecidable by giving an explicit mapping reduction. To show ...
-1
votes
3answers
167 views

Decidability of Turing Machines with input of fixed length [closed]

I'm learning about undecidability, and found this question: ...
0
votes
1answer
63 views

Can the complement of a non-recursive language be RE

I've got a problem where I need to check the validity (i.e to say whether it's true or false) of the following statement: Complement of a non-recursive language can NEVER be recognized by any ...
1
vote
1answer
54 views

Reducing from a Turing machine that recognizes is regular to the halting problem

I'm trying to understand reduction, this is from my textbook and is not a homework problem or even any exercise, just trying to understand an example they present. This is the reduction they give: ...
0
votes
0answers
29 views

Recursive set - How to show a language is undecidable [duplicate]

I am currently working on the following task: A language L = {< M> | M(x) = x^2} is given. Now I need to show, that this language is not decidable. By the way, < M> is the Gödel number But ...
2
votes
2answers
59 views

How to prove that “Total” is not recursive (decidable)

$\mathrm{Halt} = \{ (f,x) | f(x)\downarrow \}$ is r.e. (semi-decidable) but undecidable. $\mathrm{Total} = \{ f | \forall x f(x)\downarrow \}$ is not r.e. (not even semi-decidable). I need some help ...
0
votes
0answers
44 views

Using Rice's Theorem Correctly [duplicate]

I'm currently learning about Rice's Theorem, and I'm having a bit of trouble understanding when I can and cannot use it. It's my understanding that Rice's Theorem can only be applied to something if ...
0
votes
1answer
79 views

Decidability of the language that accepts a universal turing machine

Is the language $L_{universal} = \{ \left \langle M \right \rangle | M \textrm{is a universal turing machine} \}$ decidable? I'm guessing it is decidable according to the definition of a UTM, that a ...
3
votes
1answer
125 views

Can it be decided whether there exists a string accepted by a given NFA at least k ways?

Can I think this way: We can convert a NFA to a RE using GFA. We build a series of GFAs. At each step, one state (other than start or accept) is removed and replaced by transitions that have the ...
-1
votes
1answer
298 views

Is every subset of a decidable set, also decidable?

Is it true that if A is a subset of B, and B is decidable, than A is guaranteed to be decidable? I believe it would be true because all the subsets of B should also be decidable making A decidable. ...
0
votes
1answer
149 views

Infinite union of recursive languages

I'm trying to figure out how to prove or disprove the following statement: Infinite union of recursive languages is recursively enumerable. I know how to prove that infinite union of regular ...
1
vote
2answers
111 views

Is the language of DFAs which do not accept themselves recognizable?

I understand how a the language of turing machines which do not accept themselves is not recognizable but I'm not sure if the same proof could be used to describe a DFA... i.e a proof by contradiction ...
3
votes
1answer
214 views

Show that a language is RE or recursive

Consider these 2 languages: $L_{\ge5} = \left \{ \left< M \right> : M \text{ accepts at least 5 strings} \right\} $ $L_{<5} = \left \{ \left< M \right> : M \text{ accepts ...
0
votes
1answer
63 views

Recursive language with non-recursive subsets

I have a professor who is really poor at explaining the material, which is what makes answering his questions very hard. Here is the question: Recursive language with non-recursive subsets. Does ...
3
votes
1answer
42 views

Undecidability of the PCP problem with bounded width

Given two ordered sets of words $a_1, a_2, ..., a_k$, $b_1, b_2, ..., b_k$ taking values in some discrete alphabet $A$, a solution to the PCP problem is a sequence $i_1, ..., i_n$ taking values in $1, ...
0
votes
1answer
67 views

Reference for an undecidability proof [duplicate]

I'm searching for a reference of an undecidability proof that is as simple as possible and starts "from scratch". With "from scratch" I mean that it does not use some other undecidable problem to ...
1
vote
0answers
72 views

Is this an example of a type-0 grammar that is not context-sensitive?

A type-0 grammar generates a recursively enumerable (RE) language. A RE language is also known as a semi-decidable language. A semi-decidable language is a particular kind of undecidable language: ...
3
votes
2answers
111 views

Can a method be written if the language is undecidable?

If a language is decidable, we can write a method that always halts and returns true for each string that is an element of the language and ...
0
votes
1answer
502 views

Undecidable among these for turing machine

Below are two questions I found in Theory of Computation book but couldn't find its correct answers, can anyone please give correct answers with explanation? It is undecidable, whether an arbitrary ...
3
votes
1answer
110 views

Undecidability of a restricted version of the acceptance problem

It's known that the following language, the so-called acceptance problem is undecidable: $A_{TM} = \{\langle M,w\rangle\,\vert\,M\text{ is a TM which accepts }w\}$ The proof is by contradiction: ...
8
votes
1answer
172 views

Reductions among Undecidable Problems

Im sorry if this question has some trivial answer which I am missing. Whenever I study some problem which has been proven undecidable, I observe that the proof relies on a reduction to another problem ...
0
votes
1answer
344 views

Use Rice's theorem to show that the language of optimisable Turing machines is undecidable

I have an assignment to do and I'm quite stuck with the following question : Use Rice's theorem to show that $ \qquad L' = \{ \langle M \rangle \mid \; (\exists \text{ TM } M') \; [ L(M') = ...
3
votes
1answer
74 views

Hierarchy of undecidable languages

Let us define two languages of Turing machines. $$ EQ_{TM} = \{<M_1,M_2> : L(M_1) = L(M_2)\} $$ $$ ALL_{TM} = \{<M> : L(M) = \Sigma^*\} $$ It is easy to show that neither of the languages ...
1
vote
1answer
389 views

Relationship between Undecidable Problems and Recursively Enumerable languages

I have read the Wikipedia article on Recursively Enumerable languages. The article suggests that the halting problem is recursively enumerable but undecidable. My idea till today was that the halting ...
12
votes
1answer
253 views

Is it decidable if a language described by number of occurences is regular?

It is known that the language of words containing equal number of 0 and 1 is not regular, while the language of words containing equal number of 001 and 100 is regular (see here). Given two words ...
10
votes
1answer
340 views

What makes type inference for dependent types undecidable?

I have seen it mentioned that dependent type systems are not inferable, but are checkable. I was wondering if there is a simple explanation of why that is so, and whether or not there is there a limit ...