Questions tagged [undecidability]

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

Filter by
Sorted by
Tagged with
-8 votes
1 answer
522 views

Are the halting problem proofs refuted by software engineering?

This has been completely rewritten today 2022-09-16 to address all of the objections from thousands of reviews in the last 12 months. Are the halting problem proofs refuted by software engineering ? <...
0 votes
1 answer
67 views

Prove that DIFFERENTDFA, PDA {<M1, M2> | Where M1 is a DFA and M2 is a PDA where L(M1)≠L(M2)} is undecidable

I am absolutely stumped on this one. I am unsure of how to start with this one. I have thought to reducing the problem to Atm. Another thought I have had is to convert M1 to a PDA and use the ...
0 votes
1 answer
25 views

Infinite loops and the computability of mapping reductions

Consider the reduction $A_{TM} \le_m \overline{E}_{TM}$, where $$A_{TM} = \{\langle M, w \rangle \mid \text{TM $M$ accepts $w$}\}\text{, and}$$ $$\overline{E}_{TM} = \{\langle M \rangle \mid \text{TM $...
0 votes
1 answer
55 views

Proving undecidability of a language with mapping reductions

I'm referring to questions like this one: Mapping reduction to show NeverHalt is undecidable I understand with Turing reductions, you have to use oracle calls of the unknown language you're trying to ...
0 votes
1 answer
618 views

Determine if a language is Decidable or semi decidable

Consider the language $L = \{\langle M \rangle: \text{ $M$ accepts at most two single-letter words}\}$, where $\langle M\rangle$ is the encoding of Turing machine $M$. We need to determine, without ...
12 votes
2 answers
2k 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 ...
0 votes
0 answers
68 views

proof that halting problem is undecidable

In the book Formal languages and automata by Peter Linz, 4th edition (Jones & Bartlett Learning), on pages 300-301, there is a proof for the fact that the halting problem is undecidable. The proof ...
1 vote
1 answer
44 views

Is it computable to find the cardinality of intersection of two recursively enumerable sets?

I am well aware that recursively enumerable sets (which are subsets of $\mathbb N$) are closed under intersection. What is more interesting is whether or not the cardinality of the intersection is ...
1 vote
1 answer
40 views

Comparing source code and compiled code for ("topological") equivalence

Assume that I have a program Login.c that I have compiled with cc and generated the executable ...
9 votes
5 answers
28k views

How to tell if a language is recognizable, co-recognizable or decidable?

If you have a language L, without doing any proofs, is there a way to tell if it's recognizable or co-recognizable or decidable? Basically any hints or tricks that can be used to tell. Or maybe the ...
2 votes
1 answer
101 views

proof of non Turing-computable function g

In one of my lessons about turing machines I have been taught that the function g is not computable: \begin{cases}g(n)=f_{n}(n)+1 & \text { if } f_{n}(n) \text { is defined } \\ g(n)=1 & \text ...
3 votes
1 answer
68 views

Automated Query Equivalence Solver (MongoDB)

The query-equivalence problem is undecidable. However there are theorem provers that attempt to solve instances of undecidable problems. I am curious how I could go about using an automatic theorem ...
1 vote
1 answer
26 views

prove that there does not exist a Turing machine with a particular property

Prove that there does not exist a Turing machine M such that for every Turing machine K that halts on all inputs, $M$ accepts $\langle K\rangle$ if and only if $L(K)$ is infinite. The above question ...
1 vote
1 answer
536 views

Undecidability of closure under reverse of language accepted by TM

Prove that the following problem is undecidable using a reduction: Given a Turing machine $S$, does $S$ accept a word $w$ iff it accepts its reverse $w^R$? There is a solution here, which I don't ...
3 votes
1 answer
569 views

A variation of the halting problem

Given an infinite set $S \subseteq \mathbb{N}$, define the language: $L_S = \{ \langle M \rangle : M $ is a deterministic TM that does not halt on $\epsilon$, or, $T_M \in S\}$ where $T_M$ is the ...
0 votes
1 answer
69 views

Prove that the language of all Turing machines that accept finitely many words is decidable or not

Question: we have the following language: $$A = \{\langle M \rangle :| L( M)| < \infty \text{ and } M\text{ is a Turing machine}\}$$ where $\langle M\rangle$ is the encoding of $M$ and $L(M)$ is ...
0 votes
1 answer
126 views

Rice theorem could apply except RE language?

You know that Rice theorem is applicable to check decidability of RE language. Also we know that all regular, deterministic context free, context free, recursive languages are RE languages. $Q_1:$ So ...
45 votes
2 answers
20k views

How to show that a function is not computable? How to show a language is not computably enumerable?

I know that there exists 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 ...
1 vote
1 answer
72 views

a halting turing machine

Prove that there does not exist a universal Turing machine that takes a pair $\langle M, w\rangle$ as input, where M is a Turing machine and w is a string, and that always halts, accepts if $M$ ...
-1 votes
1 answer
85 views

Reasoning given with explanation of Halting Problem

I have read (and re-read) the informal proof of The Halting Problem. Can we not make the same argument using only the Program, without the Input {e.g. H(P) rather than H(P, I)}? I am confused by the ...
2 votes
1 answer
66 views

Showing that a property is semantic - Rice's theorem

I want to show that the language $$L= \left\{ \left\langle M\right\rangle \mid\substack{\text{M is a TM and there exists a poly TM $M'$ such that}\\ \text{if M halts on input $w$, $M'$ halts on $w$ ...
0 votes
0 answers
20 views

Is it a well-posed question to decide whether a process is deterministic, given that the machine is equipped with a TRNG?

Consider a machine equipped with two input devices: A true random number generator for a fair coin toss, and stdin. I wondered whether it's possible to decide that ...
0 votes
1 answer
99 views

Reduction of Turing-machine language

How to show that the following language is undecidable using reduction on the halting problem? $L: = \{w \in \{0,1\}^* |$ TM $M$ with $w = \langle M \rangle$ does not accept any input $\}$ When TM ...
2 votes
1 answer
45 views

Turing Machine writes "a" for every input w is undecidable

I have a doubt on my solution of the following: Formalize the language of a Turing machine that takes a Turing machine "M" and a character "a" as input, the language recognizes all ...
15 votes
2 answers
430 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 $...
2 votes
1 answer
182 views

Disprove: if L is decidable then Prefix(L) is decidable

The following question was sent to me by a friend and I didn't really ask him about its source so I couldn't provide the source of it. I solved the question and I need to ensure my answer not just for ...
1 vote
2 answers
59 views

Why is $A_{TM}$ not mapping reducible to $E_{TM}$?

$A_{TM}= \{ \langle M,w\rangle \mid M$ is a TM that accepts $w\}$ $E_{TM}= \{ \langle M\rangle \mid L(M) = \emptyset \}$ The standard proof for the undecidability of $E_{TM}$ is given in this ...
1 vote
1 answer
28 views

If predicate P is partially-decidable, is ¬P decidable, partially decidable or undecidable?

I was learning about decidability when I thought of this question: If P is partially decidable, is ¬P decidable, partially decidable or undecidable? I think it is Undecidable since if ¬P holds then P ...
1 vote
1 answer
54 views

Intuitive reason why the language of halting machines is Turing reducible but not many-one reducible to its complement

I have seen this statement in my studies and I cannot figure out why it is true. We know that $P_{HALT} \leq_T \overline{P_{HALT}}$, but $P_{HALT} \leq_m \overline{P_{HALT}}$ does not hold. I know, ...
1 vote
0 answers
33 views

How to show a language is not recursive, without using reductions?

I would like to show a language is in not recursive (not in the family $R$) without using a reduction from a language that is known to be non-recursive. In other words, its as if I am discovering the ...
1 vote
1 answer
72 views

Whose fault is that $\mathsf{\text{NOT-HALT}}$ is not in $\mathsf{RE}$?

An alternative way of deciding within a nondeterministic complexity class is to present a verifier-prover pair. To recall, let $\mathsf{L}$ be a language, and let $\mathsf{w}$ be a word. To decide ...
1 vote
1 answer
194 views

Undecidability in optimal data compression

There is this certain slide in Coursera Computer Science: Algorithms, Theory, and Machines course: I think it is saying finding the optimal size of given data is undecidable. However, I thought there ...
1 vote
1 answer
90 views

Proving Undecidability of this Language

Consider the language $$L = \{\langle M \rangle \mid \text{$\exists$ an input $x$, where $|x|<i$, such that $M$ halts on $x$, but it takes at least $j$ steps} \}$$ where $i$ and $j$ are fixed non-...
0 votes
1 answer
35 views

Turing recognizability and Reduction Mapping on pairs of related Turing machines

I am interested in computation and I am lost on undecidability and reductions. I have the following two problems I am stuck on. Let us call 2 Turing machines related if there is an input $w$ on which ...
0 votes
2 answers
215 views

Undecidability of TMs recognizing a decidable language

The language $L = \{ \text{M} \mid \text{M is a TM and the set of words w such that M halts on w is decidable} \}$ is given. I need to prove that $L$ is NOT Turing recognizable. I've got a hint: it ...
0 votes
1 answer
43 views

If $A ⊆ B ⊆ C$ and $A$, $C$ are decidable, then $B$ is decidable

I should prove or give a counterexample to the above statement. In my opinion, this statement is false but I don't manage to find the right counterexample. My idea was to define $C = Σ^*$ because $Σ^*$...
-2 votes
1 answer
128 views

Halting problem. Decider “recognising itself” in the input? Part 2

This is a "revision" of this question, it contained an error I now see. In a nutshell, I was wondering if in the halting problem proof the decider $D$, after recognising its source code in ...
-1 votes
1 answer
188 views

Halting problem. Decider “recognising itself” in the input?

This is about the halting problem. My questions are: where do you think are logical flaws in what I am going to write? How do you think this does not invalidate the proof for the undecidability of the ...
-1 votes
1 answer
56 views

Undecidability and Unrecognizability of Language with two Turing Machines

I've been working on undecidability proofs and I found this question in the practice problems for the textbook "An Introduction to Automata Theory." I know that we start by contradicting the ...
1 vote
1 answer
68 views

For any two languages A and B there exists J such that both A and B are Turing reducible to J

Here is the my attempt: Proof : Suppose $J = \{aa' \mid a \in A\} \cup \{bb' \mid b \in B\}$ such that $a'$ and $b'$ are the symbols that do not belong to any $w \in A \cup B$ and $a,b$ are strings. ...
1 vote
1 answer
198 views

Prove that Turing Machine ever writes a blank symbol over a non blank symbol is undecidable

I have been given the following problem from the book Introduction to the Theory of Computation by Martin Sipser and was wondering if my solution is correct: Determine if a Turing Machine ever writes ...
4 votes
2 answers
473 views

How to show that the NECESSARY_CFG is Turing-recognizable but undecidable?

I have been given the following problem and was wondering if my solution is correct: Say that a variable $A$ in CFG $G$ is necessary if it appears in every derivation of some string $w$ where $w$ is ...
3 votes
2 answers
632 views

determining whether a program halts or not

I have difficulty understanding the halting problem. I know that for all possible Turing machines and strings w, we don't have a Turing machine that can decide whether a TM M halts on input w. Now ...
1 vote
1 answer
66 views

Prove $H2 = \{\langle M\rangle : M$ accepts all inputs in $\{0, 1\}^∗$ whose length is at most $2\}$ is undecidable but recognizable

Yet another question from an exe. in the Computability class taught by Z. Luria - I'm not really sure how to prove the undecidability, moreover, didn't a finite language always decidable? I mean we ...
2 votes
1 answer
127 views

Prove it is undecidable that a Turing machine accepts at least one input w in space $|w|^2$

This question is part of the undecidable lecture by Jeff Erickson. $$\{\langle M\rangle\mid M \text{ accepts at least one string }w\text{ in space }|w|^2\}$$ We should prove that this language is ...
0 votes
2 answers
41 views

Post Correspondence Problem is undecidable

I am reading Introduction to the Theory of Computation by Michael Sipser and I am in chapter 5. It says here that the Post Correspondence Problem is undecidable, but thinking about it, given a ...
0 votes
3 answers
160 views

Can we enumerate finite sequences which have no halting continuation?

Note: this question has been cross-posted to Math.SE, after about a week here. I am trying to deepen my understanding of the relationship between the Halting Problem and Godel's Completeness Theorem (...
2 votes
1 answer
1k views

Undecidable: Given a TM $M$, is there $w$ on which $M$ halts after $\leq |w|$ steps?

The question is: Is there a word $w$ on which a TM $M$ halts after a maximum of $|w|$ (word length) steps? More formerly, is the language below decidable? $$H=\{\langle M\rangle \mid \text{ TM $M$ ...
1 vote
1 answer
57 views

Prove Language Is Undeciable Using Diagonalization

I was given the following problem and told it has to be solved using diagonalization. However, I am confused as to why diagonalization would be the solution. Would the answer not be since L is ...
-2 votes
1 answer
36 views

Decision problem

Prove the following theorem Let A and B be two languages on an alphabet Σ. If A ≤p B and B ∈ P, then A ∈ P. Could anyone be able to prove it?

1
2 3 4 5
17