Questions tagged [undecidability]

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

Filter by
Sorted by
Tagged with
7
votes
1answer
183 views

What is a list of "reasonable but undecidable" theorems?

There are some theorems that go along the lines of "all reasonable properties of <math subject> are computationally undecidable." Here are two examples: Rice's Theorem: "all ...
0
votes
0answers
118 views

How would I prove that nondeterministic Turing machines are undecidable?

How would I go about proving that the language: $$A_{NTM }= \{\langle N, w\rangle | N \text{ is a nondeterministic TM and } N \text{ accepts }w\}$$ is undecidable? I looked at the proof for $A_{TM}$ ...
11
votes
3answers
337 views

Decidability of a problem concerning polynomials

I have come across the following interesting problem: let $p,q$ be polynomials over the field of real numbers, and let us suppose that their coefficients are all integer (that is, there is a finite ...
3
votes
0answers
151 views

is it decidable whether a grammar in Chomsky normal form has useless rules?

Given a context-free grammar in Chomsky normal form, is it decidable whether that grammar has any useless rules? By "useless", I mean a rule that can be omitted from the grammar without ...
4
votes
1answer
356 views

Undecidability of "is this CFG prefix-free?"

I'm having difficulty proving undecidability of "is this CFG prefix-free?". (this proof is given as problem 5.32b in Sipser 3rd edition). Another thread has the very different question "...
5
votes
2answers
521 views

Decidability of dependent typing on primitive recursive languages

With a dependent type system in a normal functional language type checking may never halt. This is partially because dependent typing removes the isolation between types, and code. My question is this:...
1
vote
1answer
78 views

Cannot understand reductions from the halting problem and its complement

When I was going through the reductions from $HP$ and $\overline{HP}$ in this handout, I do not understand how everywhere the following claim is made: $$⟨M,x⟩ \in \overline{HP} ⇒ \text{M does not halt ...
1
vote
1answer
28 views

Not understanding this way of proving undecidability of the termination problem

I am reading some slides on Algorithm to understand why termination is an undecidable problem. The slides say the following: – Assume termination(P) always terminates and returns true iff P always ...
6
votes
1answer
374 views

Solving systems of linear equations over semirings

So I have come across an issue where it would be very nice to solve systems of linear equations over semirings but I have no clue how to do that. Over a field I would use Gaussian elimination but I'm ...
-1
votes
1answer
72 views

Is this Language decidable?

As the title says; is this language decidable and how do you prove it? $$L =\{\langle M\rangle \mid M \text{ is a Turing Machine and there is an input that } M \text{ halts on} \} $$
0
votes
1answer
124 views

Algorithmic problem of regular, context-free, and recursively enumerable languages

Consider a language $L_1$ that is recursively enumerate, $L_2$ that is regular, and $L_3$ that is context-free. Are the following problems algorithmically decidable? Is $L_1 \cap L_2 = L_3$? Is $L_1 \...
0
votes
1answer
55 views

Is $\{w~|~\forall x \in T(M_v):|w|>|x|~\}$ decidable?

I want to ask if $\{w|\forall x\in T(M_v):|w|>|x|\}$ is decidable if v is a Index of a random but fixed Turing Machine with $|T(M_v)|<\infty$. My idea: It is co-semi-decidable since as soon as i ...
1
vote
1answer
74 views

Union of every language within group of decidable languages is also decidable?

So I was trying to solve following exercise: Let $(L_{i})_{i \in \mathbb{N}}$ be a family of decidable languages - this means that every $L_{i}$ is decidable. Then $\cup_{i \in \mathbb{N}}L_{i} $ is ...
1
vote
1answer
36 views

Why is the following language undecidable?

I'm currently learning for my exams this semester and tried to solve some old exams from the last years. The question is to show, that L ist undecidable. $L=\{w|T(M_w)\neq\emptyset \land \forall x \in ...
1
vote
1answer
62 views

Is the problem that determines whenever the word member $\in$ L(M) decidable or not?

Given a Turing machine M on alphabet {m,e,b,r} we're asked to determine if member $\in$ L(M). You must realize that M is not one specific machine and can be any turing Machine with the same alphabet. ...
14
votes
2answers
398 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 $...
0
votes
1answer
42 views

Undecidability of the language of all Turing Machines with repeat strings as their language

Show that the language consisting of all Turing machines whose language consists of strings that can be broken up into two consecutive and equal strings is undecidable. I would prefer if reduction was ...
21
votes
6answers
3k views

Halting problem theory vs. practice

It is often asserted that the halting problem is undecidable. And proving it is indeed trivial. But that only applies to an arbitrary program. Has there been any study regarding classes of programs ...
1
vote
1answer
145 views

How to prove the language of all Turing Machines that accept an undecidable language is undecidable?

I want to prove that $L=\{\langle M \rangle |L(M)\text{ is undecidable}\}$ is undecidable I am not sure about this. This is my try : Suppose L is decidable. Let $E$ be the decider from $L$. Let $A$ be ...
3
votes
3answers
10k 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. I'...
16
votes
5answers
3k views

Proof of the undecidability of compiler code optimization

While reading Compilers by Alfred Aho, I came across this statement: The problem of generating the optimal target code from a source program is undecidable in general. The Wikipedia entry on ...
0
votes
1answer
46 views

Is the Post Correspondence Problem with more than two rows harder than the standard two-row variant?

The standard Post Correspondence Problem concerns tiles with two rows of symbols, and whether a tile arrangement can be made so that the sequence of the top symbols of the tiles is equal to the bottom ...
1
vote
0answers
40 views

Decidability for $ \exists w´, w´´\in L:$ so that |w´´| - |w´| is prime

I tried to decide wheter the given Language $ L = \{ \langle M \rangle | M \space is \space TM \space and \space \exists \space w´,w´´\in L(M):|w´´|-|w´| \space is \space prime \} $ is recursive or ...
0
votes
2answers
607 views

Is checking if regular languages are equivalent decidable? [duplicate]

Is this problem algorithmically decidable? L1 and L2 are both regular languages with alphabet $\Sigma$. Does L1 = L2? I think that it is decidable because you can write regular expressions for each ...
-1
votes
2answers
67 views

Proof: is the language $L_1=\{\langle M\rangle\mid\emptyset \subseteq L(M)\}$ (un)-decidable?

I want to show that $L_1 = \{\langle M\rangle \mid \emptyset \subseteq L(M)\}$ is decidable/undecidable - without rice theorem (just for the case that I can apply it). Every language contain the $\...
0
votes
1answer
631 views

What undecidable language $B$ is reducible to its complement?

I encountered a problem which asks to give an example of an undecidable language $B$ such that $B \leq_m \overline{B}$... However, I could find it hard to construct an example ... my difficulty is ...
0
votes
1answer
50 views

Is the languague L={<M>, M accepts a finite amount of words} decdidable?

Is $L=\{<M> | L(M) \ is \ finite\} $ decidable ? M is a TM. I think its relative simple to proof with the theorem of rice. But I am interested in a solution which does not use the Rice theorem. ...
1
vote
1answer
68 views

Why is this language Turing recognizable and not not-Turing recognizable

I read that the following language is r.e. but not not-Turing recognizable $L$: On input $M$ (where $M$ is a Turing Machine), $M$ accepts at least 20 inputs I am not sure why it is not not-Turing ...
1
vote
0answers
45 views

How to show that these two disjoint sets $A$ and $B$ exist

I came across this problem which asks to show the existence of two disjoint Turing-recognizable sets $A$ and $B$ such that no decidable set $C$ can separate them... In this case, a set $C$ is said to ...
0
votes
0answers
26 views

Is the emptiness of intersection of two CFLs decidable? [duplicate]

Consider $L = \{\langle L_1, L_2\rangle\mid L_1, L_2 \in \text{CFL} \text{ and } L_1 \cap L_2 = \emptyset \}$. How to prove that $L \notin R $? $L_1, L_2$ encoded in chomsky-normal-form.
0
votes
1answer
30 views

Help me understand this Turing-machine Problem concerning $A_{TM}$

I'm a Physics/C.S. student and have been struggling with this particular problem for a few days now. So the task is as following: Consider the following languages: $\hspace{20pt} L_1 = \{\langle M \...
1
vote
1answer
179 views

Check if language is decidable

I would like to determine if the following language is decidable or not. L = { w $\in$ $\Sigma^*$ | $T(M_w)$ is recognized by a Turing machine with at most 42 states}. I know that every finite ...
-1
votes
1answer
15 views

Is the Languague which contains all TMs which write the blank symbol at firs by the given input w decidable?

Consider the problem of determining whether a Turing machine M on an input w writes the blank symbol at first. Is this decidable ?
0
votes
1answer
99 views

Show that for every language there exists a harder language

I came across this problem that I could not figure out... For every language $A$, there is supposed to be a language $B$ such that: $$ A \leq_T B $$ but: $$ B \not \leq_T A $$ If it is $A \leq_TB$ and ...
0
votes
1answer
48 views

Is $L_2:=${$<M>$|$L(M)=\overline{A_TM}$} (un-)decidable?

I have to prove that the language $L_2:=${$<M>$|$L(M)=\overline{A_TM}$} is (un-)decidable. In a previous assignment we proved that $L_1:=${$<M>$|$L(M)=A_TM$} is undecidable. I would say ...
24
votes
1answer
2k views

What are the strongest known type systems for which inference is decidable?

It's well known that Hindley–Milner type inference (the simply-typed $\lambda$-calculus with polymorphism) has decidable type inference: you can reconstruct principle types for any programs without ...
1
vote
0answers
43 views

difference between two uncomputable functions

for $L1$ regular language, $L2$ some language, $L1$ \ $L2$ is regular, decidable. yet, the next transition function might not even be computable: $F′=${$\,q:δ(q,w)∈F \, for\, some\, w∈ L2\,$}$.$ $F$ ...
0
votes
1answer
48 views

Proving undecidability for a language which contains string with certain syntax

Lets say we have the following problem: $$\mathcal{L}_1 = \{\langle \mathcal{M} \rangle | \mathcal{M}\ \text{is a Turing machine and $\mathcal{L}(\mathcal{M})$ contains a string with exactly three ...
1
vote
1answer
172 views

How to decide whether a language is decidable when not involving turing machines?

For instance, consider L = {k : the binary expansion of sqrt(2) contains k consecutive 1s}. Obviously Rice Theorem would not work. I also tried the method of how it is to PCP undecidable but still no ...
1
vote
1answer
134 views

Is there a language that cannot be polynomially reduced to?

Is there a language A that cannot be polynomially reduced to by some language B? Or is it always possible to reduce a language B to A?
-2
votes
2answers
109 views

Is a 'discrete language' well-defined?

Are the following well-defined formal languages (in these cases: subsets of {0,1}*) ? An argument w is a member of L under the following rules... Example1: If more than half of w's digits are 1's --...
0
votes
1answer
53 views

Is $nHALT$ undecidable even if $M$ halts on input $w$ in finite steps

If we have the language $nHALT=\{<M,w,n>;$ $M$ halts on input $w$ in less than $n$ steps$\}$ Is this language also undecidable in the same way that $HALT$ is undecidable? And if so, $nHALT\...
2
votes
1answer
22 views

Decidability of a language and inclusion between two other languages

I have this assignement that asks to say if the following statement is true or false, and possibly justifying the answer: "Let L₁, L₂ be decidable languages. For every language L s.t. L₁ ⊆ L ⊆ L₂, L ...
1
vote
3answers
2k views

What does "Every CFL is decidable" exactly mean?

I am trying to prove the fact that every CFL is decidable, however I can't come to terms with what the statement exactly means. I know that generation of a particular string by a given CFG is a ...
2
votes
1answer
49 views

Decide if a language has a word of a given size

Suppose that $L$ is some language over the alphabet $\Sigma$. I was asked to show that the following languages is decidable: $$L' = \{w \in \Sigma^* | \text{ there exists a word } w'\in L \text{ ...
1
vote
1answer
720 views

Decidability of Turing machines that never move their heads past any input string

$L_1 = \{ \langle M, w\rangle : M \text{ is a TM that never moves its head past the input string } w \}$ $L_2 = \{ \langle M\rangle : M\text{ is a TM that never moves its head past any input string} ...
3
votes
1answer
62 views

Decidability of equality, and soundness of expressions involving elementary arithmetic and exponentials

Let's have expressions that are composed of elements of $\mathbb N$ and a limited set of binary operations {$+,\times,-,/$} and functions {$\exp, \ln$}. The expressions are always well-formed and form ...
0
votes
0answers
65 views

Is the undecidability of a given problem undecidable?

Given an input problem P, can you construct an algorithm A to compute whether or not P is decidable or undecidable? In other words, is the undecidabiliy of a problem undecidable? My initial guess is ...
2
votes
1answer
280 views

Turing machine with an oracle for a proper subset of a known undecidable language

Consider a Turing machine $T$ with access to an oracle for a proper, nonempty subset of $A_{TM}$, say $L$. That is, $T$ can query this oracle to check whether some string belongs or doesn't belong to $...
0
votes
1answer
42 views

About computable sets

Let TOT be the set of all Turing Machines that halt on all inputs. Find a computable set B of ordered triples such that: TOT = {e : ($\forall$x)($\exists$y)[(e, x, y) $\in$ B] This definition means ...

1 2
3
4 5
16