Questions tagged [undecidability]

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

Filter by
Sorted by
Tagged with
43
votes
2answers
15k views

How to show that a function is not computable?

I know that there exist a Turing Machine, if a function is computable. Then how to show that the function is not computable or there aren't any Turing Machine for that. Is there anything like a ...
137
votes
3answers
15k views

How can it be decidable whether $\pi$ has some sequence of digits?

We were given the following exercise. Let $\qquad \displaystyle f(n) = \begin{cases} 1 & 0^n \text{ occurs in the decimal representation of } \pi \\ 0 & \text{else}\end{cases}$ ...
38
votes
2answers
7k views

Perplexed by Rice's theorem

Summary: According to Rice's theorem, everything is impossible. And yet, I do this supposedly impossible stuff all the time! Of course, Rice's theorem doesn't simply say "everything is impossible". ...
31
votes
7answers
6k 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 ...
19
votes
2answers
11k views

Is the set of Turing machines which stops in at most 50 steps on all inputs, decidable?

Let $F = \{⟨M⟩:\text{M is a TM which stops for every input in at most 50 steps}\}$. I need to decide whether F is decidable or recursively enumerable. I think it's decidable, but I don't know how to ...
11
votes
6answers
26k views

Can a Turing machine decide the language $L_\emptyset$ of machines with empty language?

Let $$L_\emptyset = \{\langle M\rangle \mid M \text{ is a Turing Machine and }L(M)=\emptyset\}.$$ Is there a Turing machine R that decides (I don't mean recognizes) the language $L_\emptyset$? It ...
11
votes
1answer
1k views

Are there any existing problems that wouldn't be solvable with a halting oracle?

I understand that most problems are trivial if a halting oracle is available (or, I think equivalently, hyper-computation). However, applying the argument that shows the Halting Problem is impossible ...
18
votes
5answers
969 views

Is it possible to solve the halting problem if you have a constrained or a predictable input?

The halting problem cannot be solved in the general case. It is possible to come up with defined rules that restrict allowed inputs and can the halting problem be solved for that special case? For ...
11
votes
1answer
759 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 ...
42
votes
1answer
5k 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 ...
24
votes
4answers
1k views

Do undecidable languages exist in constructivist logic?

Constructivist logic is a system which removes the Law of the Excluded Middle, as well as Double Negation, as axioms. It's described on Wikipedia here and here. In particular, the system doesn't ...
4
votes
1answer
7k views

Is the language of Turing Machines that halt on every input recognizable?

I am trying to reduce the complement of the HALTING problem (WLOG, the complement of the HALTING problem is the language of TMs that loop on some string w)to this language in order to show that it is ...
30
votes
1answer
2k views

Rice's theorem for non-semantic properties

Rice's theorem tell us that the only semantic properties of Turing Machines (i.e. the properties of the function computed by the machine) that we can decide are the two trivial properties (i.e. always ...
7
votes
1answer
5k 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 ...
3
votes
2answers
7k 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'...
3
votes
1answer
397 views

Construction of the complement of universal Turing machine - where is the catch?

This is pretty fundamental but I'm getting confused. Let $U$ be the Universal Turing Machine and $L_{u}$ the language it accepts which is recursively enumerable. Obviously we are not able to construct ...
1
vote
1answer
585 views

Palindromes and linear grammars

Given a linear grammar G, is it possible to determine if L(G) contains a palindrome?
13
votes
3answers
1k views

Is Deciding Decidability Decidable?

I am wondering if deciding the decidability of problem is a decidable problem. I am guessing not, but after initial searches I cannot find any literature on this problem.
7
votes
3answers
4k views

Are all undecidable/uncomputable problems reducible to the Halting problem? [duplicate]

Theory of computation tells us that there are some languages that cannot be recognized by a Turing machine. That is, there are well-defined problems for which no Turing machines can provide an ...
8
votes
2answers
2k views

How do I show that whether a PDA accepts some string $\{ w!w \mid w \in \{ 0, 1 \}^*\}$ is undecidable?

How do I show that the problem of deciding whether a PDA accepts some string of the form $\{ w!w \mid w \in \{ 0, 1 \}^*\}$ is undecidable? I have tried to reduce this problem to another undecidable ...
13
votes
3answers
5k 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 ...
10
votes
4answers
5k views

Is there an undecidable finite language of finite words?

Is there a need for $L\subseteq \Sigma^*$ to be infinite to be undecidable? I mean what if we choose a language $L'$ be a bounded finite version of $L\subseteq \Sigma^*$, that is $|L'|\leq N$, ($N \...
12
votes
1answer
669 views

Program synthesis, decidability and the halting problem

I was reading an answer to a recent question, and sort of a strange, ephemeral thought came to mind. My asking this might betray either that my theory chops are seriously lacking (mostly true) or that ...
7
votes
2answers
2k views

Prove REGULAR_TM is undecidable

I am studying the proof of the following theorem: Given the language $\mathit{REGULAR}_\mathit{TM} = \{\langle M \rangle | M $ is a turing machine and $\mathit{Accept}(M)$ is regular$\}$ $\mathit{...
5
votes
3answers
3k views

Testing two DFAs generate the same language by trying all strings upto a certain length

Given the language $EQ_{\mathrm{dfa}} =$ $\{\langle A, B\rangle\mid A$ and $B$ are two DFAs and $L(A) = L(B)$ $\}$ Prove that $EQ_{\mathrm{dfa}}$ is decidable by testing the two DFAs on all strings ...
4
votes
1answer
346 views

Undecidability of REGULAR_TM (Detail within Proof)

I'm reading through Sipser's Intro to the Theory of Computation for a class, and I'm having trouble understanding one of the examples in the book. The example shows how $REGULAR_{TM}$, defined as the ...
4
votes
2answers
1k views

Is undecidable(complement of R) a subset of NP-hard?

Is there an undecidable problem which is not NP-hard?
3
votes
1answer
252 views

Machines whose languages are their own encoding

Is the language $S = \{\langle M \rangle \mid M \text{ is a Turing Machine and } L(M) = \{\langle M \rangle\}\,\}$ decidable, recognizable and/or co-recognizable? I tried diagonalization but can only ...
3
votes
1answer
2k 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: ...
6
votes
1answer
1k views

Is it decidable whether a Turing machine modifies the tape, on a particular input?

Is $L=\{\langle M,w \rangle|M\text{ does not modify the tape on input w}\}$ decidable? We could tell if a TM does not modify the tape on any input by checking if there are no transitions in $M$ that ...
0
votes
1answer
2k views

Is it decidable if a TM takes at least 2016 steps on all inputs?

$$L_1= \{\langle M \rangle \mid \text{\(M\) takes at least 2016 steps on all inputs} \}$$ Is this language decidable? I will write my way of understanding it. Please answer it in the way I ...
-2
votes
1answer
308 views

Prove that {⟨M,w⟩∣M accepts w only} is unrecognizable [closed]

$$L = \{\langle M,w\rangle \mid \text{\(M\) accepts \(w\) only}\}$$ How can I prove this language is unacceptable (unrecognisable)? I think I should use a reduction, I'm not sure how.
10
votes
2answers
4k views

A Question relating to a Turing Machine with a useless state

OK, so here is a question from a past test in my Theory of Computation class: A useless state in a TM is one that is never entered on any input string. Let $$\mathrm{USELESS}_{\mathrm{TM}} = \{\...
3
votes
2answers
4k 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 ...
1
vote
1answer
2k 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
1answer
137 views

Prove that $H$ reduces to $H\varepsilon$

I have to prove that $H_\varepsilon = \{<M> \mid M\ \text{halts on input }\varepsilon\}$ reduces to $H$ (the halting problem). I am very confused how to PROVE it, I mean it is clear that we can ...
1
vote
2answers
564 views

Is it decidable that a context free language contains a given regular language?

I've been asked to solve this problem, but I'm completely stuck now. Is the set $\{G \in\text{CFG} \mid L(G)\supseteq L(A) \}$ where A is DFA fixed beforehand decidable? I know I've to find a ...
1
vote
1answer
507 views

Reducing the infinite language problem to halting problem

Let: $INF = \{ w \in \Sigma^* | \quad |L(M_w)| = \infty \} $. It is easy to show with Rices theorem that $INF$ is not decidable. ($INF$ is non-trivial because of $\emptyset$ and $\Sigma^*$). How ...
1
vote
2answers
64 views

A special case of subset sum

I came across the following problem in my complexity-theory course: Given a set of numbers $A := \{a_1, \dots, a_n\} \subset_{\mathrm{finite}} \mathbb{N}$ and a number $b$ also in $\mathbb{N}$ such ...
0
votes
1answer
63 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, ...
0
votes
1answer
505 views

A second question on “Show a TM-recognizable language of TMs can be expressed by TM-description language of equivalent TMs” [duplicate]

Let B={M1,M2,...} be a Turing-recognizable language consisting of TM descriptions. Show that there is a decidable language C consisting of TM descriptions s.t. every machine in B has an equivalent ...
0
votes
1answer
989 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 undecidable?...
-1
votes
1answer
1k views

Complement of halting set is not r.e

suppose we don't know that Halting problem is not recursive. I want to prove that complement of halting set is not r.e. then we can find halting problem is not recursive. Can you direct prove that ...
-2
votes
1answer
1k views

Is the set of TMs that accept exactly two strings (each) semi-(decidable)?

I have found this problem- let A be the set of encoding of all those Turing machines that accept exactly two strings and let A' be the complement of A. Comment on whether A and A' are recursive , ...
25
votes
5answers
10k views

Why isn't this undecidable problem in NP?

Clearly there aren't any undecidable problems in NP. However, according to Wikipedia: NP is the set of all decision problems for which the instances where the answer is "yes" have [.. proofs that ...
6
votes
1answer
8k 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 ...
20
votes
1answer
477 views

Ratio of decidable problems

Consider decision problems stated in some “reasonable” formal language. Let's say formulae in higher-order Peano arithmetic with one free variable as a frame of reference, but I'm equally interested ...
23
votes
2answers
984 views

Is there a “natural” undecidable language?

Is there any "natural" language which is undecidable? by "natural" I mean a language defined directly by properties of strings, and not via machines and their equivalent. In other words, if the ...
10
votes
2answers
996 views

Halting problem without self-reference

In the halting problem, we are interested if there is a Turing machine $T$ that can tell whether a given Turing machine $M$ halts or not on a given input $i$. Usually, the proof starts assuming such a ...
9
votes
2answers
979 views

For any language $A$, there is $B$ such that $A \le _T B$ but $B \nleq _T A$

I am trying to come up with a proof for the following: For any language $A$, there exists a language $B$ such that $A \le_{\mathrm{T}} B$ but B $\nleq_{\mathrm{T}} A$. I was thinking of letting $B$...