Questions tagged [undecidability]

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

Filter by
Sorted by
Tagged with
0 votes
1 answer
27 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 $...
  • 101
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 ...
  • 89
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 ...
  • 121
1 vote
1 answer
41 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 ...
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 ...
  • 89
1 vote
1 answer
27 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 ...
0 votes
1 answer
74 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 ...
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$ ...
2 votes
1 answer
68 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$ ...
  • 161
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 ...
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 ...
  • 121
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 ...
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
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
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 ...
  • 163
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 ...
  • 1
1 vote
1 answer
91 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
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 $Σ^*$...
  • 117
-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 vote
1 answer
69 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
201 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 ...
  • 181
4 votes
2 answers
479 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 ...
  • 181
2 votes
1 answer
140 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 ...
  • 21
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 ...
  • 117
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
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 ...
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
1 vote
1 answer
44 views

Why is the language containing the Turing machines which only accept their own encoding not applicable to the diagonalization proof?

I saw this question and asked myself why the original problem is not solvable through diagonalization. Let $$L = \bigl\{\langle M \rangle \mid L(M) = \{\langle M\rangle\}\bigr\}$$ Take the complement $...
  • 13
0 votes
1 answer
44 views

Decidability of a given grammar if it is regular

According to my course the question "Is $L(G)$ regular?" undecidable. But I was more interested in knowing the exact algorithm or proof that makes this question undecidable. To further ...
2 votes
1 answer
91 views

Why is $E_{LBA}$ undecidable if $A_{LBA}$ is decidable

A linear bounded automaton (LBA) is a restricted TM with finite tape. Let $A_{LBA} = \{\langle M, w \rangle | M$ is an LBA that accepts string $w \}$. It can be shown that $A_{LBA}$ is decidable: ...
0 votes
1 answer
39 views

Does proving undecidability implies that H is RE-Complete

If I want to show that H is RE-Complete is it enough to show it's undecidable? or should I prove something else alongeside? $H$ is the halting problem: $H = \{<p,x>|p \textit{ halts on } x\}$\
  • 197
2 votes
2 answers
465 views

Why is a Language L(M) {has at least 10 strings} turing recognizable and L(N) {has at most 10 strings} is not?

Why is a Language L(M) {has at least 10 strings} recognizable and L(N) {has at most 10 strings} is not? ...
  • 131
1 vote
1 answer
50 views

Is proving NP-(in)completeness generally NP-complete?

Is even distinguishing between NP complete and incomplete problems an NP-hard problem?
  • 181
0 votes
0 answers
44 views

Finite Number of Turing Machines that stop after k steps?

For this question suppose Alphabet for input is {0,1}. Given: L={<M> | M stops on every input after maximum 1000 steps} My professor claimed that there is a ...
  • 61
2 votes
1 answer
71 views

Is the language of PSPACE Turing Machines decidable?

Let $$L_{\text{PSPACE}}=\{\langle M\rangle : M \text{ is a TM using a polyspace amount of memory}\}$$ Is $L_{\text{PSPACE}}$ decidable? I don't think we can use Rice's Theorem because this doesn't ...
  • 293
1 vote
1 answer
64 views

Decidability for intersection of context free and regular languages

I am wondering if the following are decidable or undecidable and why. L is a CFL and R is a regular language. How does the complement of the context-free language change the decidability of the ...
0 votes
0 answers
32 views

Undecidability of a set of Turing Machines

Considering the following set, I have to say if it is undecidable, decidable or semidecidable: $$S_1 = \{y | \forall n \text{ the Turing Machine } M_y \text{ does not accept any string of length } n\}$...
0 votes
1 answer
25 views

What is the meaning of Sub_tm in this context?

Im working on a problem for a homework assignment in finite automata, but I'm having trouble conceptually grasping the problem in the first place. Prove that the following is undecidable: $SUB_{TM} = \...
1 vote
0 answers
17 views

Proving set of register machines that halt before k steps for some input is non-recursive

Given an enumeration of register machines $R_n$ that take a single natural number as input, and a constant $k$, the function $f$ is defined as: $$ f(n) = \begin{cases} 1 & \exists m \text{ such ...
  • 11
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 ...
-2 votes
1 answer
250 views

Halting problem is undecidable proof-:

Confused with this proof. I will point my confusions here. what is R(M)? They say it is representation of turing machine but what is it exactly? Is it tuples of turing machine? How do we decide w is ...
  • 47
1 vote
1 answer
32 views

The recognizability of $\overline{A}_{TM}$

In undergrad theory classes, the idea of decidability and recognizability is introduced. It's well known that $A_{TM}$, the set of words accepted by a TM $M$, is recognizable but not decidable. We ...
-1 votes
1 answer
46 views

Does Turing machine move left on particular input?

We know that RE language is the collection of unrestricted grammar which is known as type-0 grammar that's why emptiness, finiteness of every RE languages is undecidable. My question is how I check ...
  • 1
0 votes
1 answer
208 views

Why REC languages is undecidable under emptiness and finiteness?

Membership problem of Recursive languages are decidable. My approach: Let $L$ be a recursive language and $M$ be the Turing Machine that accepts it. For string $w,$ if $w ∈ L,$ then $M$ halts in ...
  • 1
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 ...
  • 1
0 votes
2 answers
257 views

Regularity of CFG and DCFL

I read that it is undecidable whether, given a CFG $G$, $L(G)$ is regular. And there exists no algorithm that, given a CFG $G$ such that $L(G)$ is regular, outputs a DFA that accepts $L(G)$. My ...
  • 1
0 votes
1 answer
97 views

Why finiteness problem of CFL is decidable?

We know that every $CFL$ has infinite configuration space. Due to this equality problem is undecidable. But why finiteness property is decidable inspite having infinite configuration space?
  • 1

1
2 3 4 5
17