Questions tagged [undecidability]

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

Filter by
Sorted by
Tagged with
1
vote
1answer
198 views

Decidability of $E_{TM}$ and $A_{TM}$ for “erasing” Turing machines

Why is the $A_{ETM}$ for a variant of a Turing machine (an erasing Turing machine), where changing a tape symbol to a nonblank symbol is prohibited, decidable? Why does the following diagonalization ...
2
votes
1answer
638 views

Decidability of equivalence of two context free grammars

I got a question regarding the decidability of equivalence of two context free grammars: Construct a Turing machine that decides whether $L(G) = L(H)$, where $G$ and $H$ are two context free ...
2
votes
1answer
83 views

How to reduce a problem?

I am a bit confused on how to reduce a problem. I'll give an example: Let's say there is a problem called HALTEMPTY and we know it is undecidable. $HALTEMPTY_{TM} = \{\langle M\rangle \mid M \text{ ...
1
vote
1answer
42 views

Problems with decidability open (for a long time) proven decidable

It seems to me that problems whose dedicability remains open for a long time, if resolved, tend to end up being undecidable. A prominent example would be (e.g.) Hilbert's tenth problem, whose ...
3
votes
1answer
121 views

Is {<M,w>|M prints more than 300 non-blanks on input w} decidable?

Let $$ L_{300}=\{\langle M,w\rangle \mid M\text{ prints more than }300\text{ non-blanks on input }w\}.$$ Is $L_{300}$ decidable? My intuition is it is decidable because given $M$ and $w$, we need ...
1
vote
1answer
283 views

Prove that it is undecidable whether a given LBA accepts a regular set

I know for an LBA the emptiness problem is undecidable. However I am not clear on how to reduce the halting problem of Turing machines to this as LBAs are strictly computationally less powerful than ...
-1
votes
1answer
84 views

Solving problems that DTM can't solve

Let L be a problem that DTM can't solve. Can we prove that there is an abstract machine that can solve this problem? Here, L is not Halting problem or Hilbert's tenth problem (because we proved that ...
3
votes
2answers
948 views

PCP undecidability

There is a popular proof for the undecidability of the PCP (Post correspondence problem), which is outlined here: https://en.wikipedia.org/wiki/Post_correspondence_problem I'll assume whoever will ...
1
vote
1answer
41 views

How to start solving this type of exercise: Determine if $L$ is in $RE\setminus coRE$ or $coRE\setminus RE$ or $R$ or not in $RE\cup coRE$?

I'm asking this, because in every exercise I check if I can relate it to one of the things I know, like:$A_{TM}$, $\overline{A_{TM}}$, ${HALT_{TM}}$,$\overline{HALT_{TM}}$, $E_{TM}$, $\overline{E_{...
2
votes
1answer
986 views

Determining if given languages are regular or recursively enumerable

I came across following problem: Suppose $L_1$ and $L_2$ are two languages, $M$ is a Turing machine $L_1 =\{M|M$ accepts at most 2016 strings$\}$ $L_2=\{M|M$ accepts at least 2016 strings$\}$ ...
0
votes
3answers
621 views

Prove or disprove if $L_{1}$ is undecidable and $L_{2}$ is finite language then $L_{1} \cup L_{2}$ is undecidable

I tried to prove by contradiction. $L_{1}$ is undecidable and $L_{2}$ is finite language then $\overline{L_{1}}\cap \overline{L_{2}}$ is decidable. $$L_{1} = \overline{HALT_{TM}} = \big\{ \langle M, ...
1
vote
1answer
79 views

Artificial intelligence and undecidibility

Can artificial intelligence solve problems like Post correspondence problem?
1
vote
1answer
106 views

Obtaining a computational history of a Turing Machine

I am currently reading the proof presented in Sipser's "Theory of Computation" for the undecidability of the problem of checking whether the language accepted by a linear bounded automata is empty. In ...
2
votes
1answer
292 views

Rice's theorem application on a language that resembles ETM

I'm working on an exercise that involves checking if the Rice's theorem can be applied on a two languages. The first language is $E_{TM} = \{ \langle M \rangle \text{ | M is a Turing Machine and } L(...
1
vote
2answers
77 views

Does the undecidability of the halting problem require Turing Machines to be enumerable?

I (think I) understand the enumeration and then diagonalization proof of the undecidability of the halting problem, but I came cross this proof in SICP below, which does not seem to require the ...
2
votes
0answers
28 views

Do undecidable problems have no HO query? If so, could I have an example?

In descriptive complexity, HO corresponds to ELEMENTARY. ELEMENTARY is a subset of R, so therefore all HO queries are decidable. Then undecidable problems have no corresponding HO query. Is my ...
1
vote
1answer
244 views

undecidability of virus detection

I have been reading the following document about the undecidability of virus detection, available at: https://enterprise.comodo.com/whitepaper/Impossibility_of_Virus_Detection_WP.pdf the problem ...
1
vote
1answer
172 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
1answer
338 views

Turing machine that does not halt on any input

I'm struggling to find a way to show that $$T = \{ \langle M \rangle\mid M \text{does not halt on any input}\}$$ is undecidable. Should I use reduction? If so, reduce this to what &ndashp ...
1
vote
1answer
288 views

A question about proving Rice's Theorem by reducing it to the Halting Problem

I've read the definition for Rice's Theorem, here's the one from Wikipedia: In computability theory, Rice's theorem states that all non-trivial, semantic properties of programs are undecidable. ...
3
votes
1answer
557 views

Can a weaker version of the Halting Problem be solved?

I've been learning about the Halting Problem and the proof that it is undecidable in its general case. The proof that it cannot be solved generally goes something like this: Assume that some machine $...
0
votes
0answers
64 views

Decidability of language that contains all TM encodings that accept at least one word

I have a language that contains all encodings of the Turing machines that accept at least one word. Is this language recursive, recursively enumerable, or neither?
2
votes
0answers
42 views

The decidability of a problem involving univariate integer polynomials

Suppose that we are given $f_1(x),...,f_n(x) \in \mathbb{Z}[x]$. Decide whether there exist $a_1,...,a_n \in \mathbb{Z}$ such that $\sum_{i=1}^{n} a_if_i(x) = p(x)^2 $ $p(x) \in \mathbb{Z}[x]$. ...
1
vote
1answer
1k views

Proving that DFA equivalence is decidable

The following question is taken from Sipser: Prove that $EQ_{\mathsf{DFA}}$ is decidable by testing the two DFAs on all strings up to a certain size. Calculate a size that works. Here is the ...
0
votes
0answers
27 views

Prove that a language is undecidable by reducing HALT to it [duplicate]

Let $L = \left\{ \langle \alpha, x\rangle \mathrel{}\middle|\mathrel{} \textrm{x is the only string accepted by}\mathrel{}M_\alpha \right\}$ and $HALT = \left\{ \langle \alpha, x\rangle \mathrel{}...
2
votes
0answers
31 views

Nearest codeword in a translation-invariant code over $\mathbb{Z}^d$

Let $c_1,...,c_n,c':\mathbb{Z^d}\rightarrow \{0,1\}$ all have finite support. Let $C$ be the linear, shift-invariant code generated by $c_1,..,c_n$. It is possible to calculate the nearest codeword $...
0
votes
1answer
835 views

Are the implications of the diagonalization language different from those of the halting problem? [duplicate]

Revised: In my previous question, I was confused about the implications of the diagonalization language. I concluded that it proves there are languages for which there are no recognizable turing ...
0
votes
1answer
379 views

Language Decidability

What is the easiest and the most straightforward way to find whether a given language is decidable? For example, how do we know if the following languages are decidable or not? ...
0
votes
0answers
27 views

How to prove that a language of machines accepting a fixed string is decideable? [duplicate]

Is L = $\{\langle M,w\rangle \mid \text{$M$ accepts string epsilon or string $w$, or both} \}$ decidable? I attempted to use Rice's Theorem for this question to prove that it is undecidable. Is my ...
1
vote
1answer
1k views

Is L={<M>|M is a TM and L(M) is uncountable} decidable?

Is $L=\{\langle M\rangle\mid \text{$M$ is a Turing machine and $L(M)$ is uncountable}\}$ decidable? My intuition is that it is not, but I'm not sure if Rice's Theorem applies in this case. If it is ...
2
votes
1answer
367 views

Halting problem for polynomial space bounded Turing machines

A polynomially bounded Turing machine is the one which, on input $w$, uses no more than $f(|w|)$ cells on its tape, where $f$ is a polynomial. For this problem halting is decidable. I do not ...
0
votes
0answers
121 views

How to Prove Undeciability of Overwriting x with y

Studying for an exam and considering the general set of languages that solve the problem of whether or not some condition is fulfilled while processing a string. I consider the language L_overwrite ...
0
votes
1answer
93 views

Show that the following language is not recursive:

$L = \{w \mid M_w \text{exists and it accepts a word } x_1 = 0x \text{ if and only if it accepts } x_2 = 1x\}$ ($x \in \Sigma^*$, so $x_1$ is starting with a 0 and $x_2$ is obtained from $x_1$ by ...
2
votes
1answer
340 views

Is the language of all deciders recognizing empty language decidable?

I TA for a course in theory of computation and this came up as an interesting question. $E_{TM}$ is the set of TM descriptions where the machine's language is empty. Of course, $E_{TM}$ is ...
3
votes
1answer
134 views

Can the higher-order oracle Turing machines simulate the lower-order machines so that the current oracle does not contradict the simulated oracle?

Here is a quote from the Source 1: For example, if $M$ is a machine with an oracle for the halting problem, then obviously there isn't in general an equivalent machine that can simulate the ...
1
vote
2answers
141 views

The set of valid sentences in FO is not decidable as a consequence of rec. inseparability

Two given languages $L_1$ and $L_2$ are called recursively separable iff there exists a recursive languge $R$ such that $L_1 \subseteq R$ and $L_2 \cap R = \emptyset$. Now consider first order logic, ...
6
votes
1answer
159 views

Relation between “undecidability of arithmetic” and “godel's incompleteness theorem”?

There is a theorem that states that arithmetic is undecidable: i.e. $Th(\mathcal N)$, the set of all sentences in the standard arithmetic structure $\mathcal N=(\mathbb N,+,\cdot , 0,1)$ where the ...
1
vote
1answer
254 views

Reduce ATM to the language of TM encodings concatenated by a string where the TM accepts both the string and its reverse

Prove that the language $LM =\{\langle M,x\rangle\mid \ M \text{ accepts }x\text{ and rev}(x) \}$, where $\mathrm{rev}(x)$ is the reverse of the string $x$, is undecidable with a reduction from $A_{\...
1
vote
1answer
783 views

How to reduce halting problem to the problem of whether a Turing Machine accepts infinitely many inputs?

The language $\{w \mid w \in \{0,1\}^{*}\text{ and }M_w\text{ accepts infinitely many inputs}\}$ is undecidable, where $M_w$ is the Turing machine represented by $w$. I am confused because I do not ...
0
votes
1answer
644 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 ...
2
votes
1answer
5k views

Show that a language is decidable iff some enumerator enumerates the language in lexicographic order

The proof is given in the below: If $A$ is decidable, the enumerator operates by generating the strings in lexicographic order and testing each in turn for membership in $A$ using the decider. Those ...
0
votes
1answer
75 views

Given three languages L1 L2 L3 that do not intirsect could one be TR and the other TD and the third neither

where $L_{1} \cup L_{2} \cup L_{3} = \sum^{*}$ and $L_{1} \cap L_{2} = \emptyset$ and $L_{2} \cap L_{3} = \emptyset$ and $L_{1} \cap L_{3} = \emptyset$ is it possible that $L_{1}$ is decidable, $L_{...
1
vote
1answer
634 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 ...
0
votes
1answer
1k views

Is L={0,1}* without strings that start with 00 decidable?

Say you have a language L = "{0,1}* without strings that start with 00". How do you prove this is decidable? I'm drawing a blank on this one.
1
vote
2answers
436 views

Is the Rice's theorem applicable to $\{ \langle M \rangle \mid M \mbox{ is a Turing machine such that }L(M) = H_{all} \mbox{ } \}$?

Until just now I thought that I have fully understood Rice's theorem but this example irritates me: $L^* = \{ \langle M \rangle \mid M \mbox{ is a Turing machine such that }L(M) = H_{all} \mbox{ } \}...
1
vote
1answer
1k views

What is the difference between undecidable language and Turing Recognizable language?

I was wondering what is the difference difference undecidable language and Turing recognizable language. I've seen in some cases where they ask: Prove that the language $ A_{TM} = \{ \ <M,w> | \...
1
vote
1answer
57 views

prove every language got a language that is harder

I am prety stuck over here: prove or disprove that every $L$ got $L'$ s.t $L'\geq L$ and for every $L''\geq L$ $L''\ngeq L'$ basically it means L' is the hardest... my intuition tells me that this ...
-1
votes
1answer
1k views
1
vote
1answer
732 views

L = { <M>, M is a DFA accepting all strings except finitely many

Is the $L$ = { $<M>$, $M$ is a DFA accepting all strings except finitely many. } decidable ? I am sort of confused about the question - what exactly does $M$ accept. How are those finitely many ...
5
votes
1answer
208 views

Analogy between Gödel's incompleteness proof and Richard's argument

If we take a look at Gödel's paper “On formally undecidable propositions”, the first self referential proof given in the paper, with the following formula: $$n \in K \equiv \overline{\textit{Bew}}[R(...

1
3 4
5
6 7
15