Questions tagged [undecidability]

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

96 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
4
votes
0answers
55 views

How to prove that the problem $\text{"If $L$ is a context-free language, then, is $\overline{L}$ also context-free?"}$ is undecidable?

Lately I came across a problem: $\text{"If $L$ is a context-free language, then, is $\overline{L}$ also context-free?"}$ And I need to comment on its decidability. Now I know that context free ...
4
votes
0answers
46 views

Modern presentation of Ackermann's "Solvable Cases?"

Ackermann's book "Solvable Cases of the Decision Problem" discusses decidable instances of first order logic, particularly monadic logic, and so called "equality formulas". However, the book is from ...
4
votes
1answer
145 views

Proving a certain superset the halting language is not recursive

Let $\Sigma =\{ 0, 1\}$. Let $val:\Sigma^* \rightarrow \mathbb{N}$ be a function that given a string returns its decimal value, and $L_{halt} = \{\langle M\rangle \langle w\rangle \mid M $ halts on $w ...
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 ...
3
votes
1answer
444 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 ...
3
votes
0answers
107 views

Undecidability of language involving two TMs

I am currently browsing the lecture notes on computability/decidability and I have encountered the following exercise I am unable to solve. Given $M_1$, $M_2$ Turing machines, is it true that for ...
3
votes
0answers
60 views

Hamming connectivity of regular languages

Call a language $L$ Hamming connected iff, for every pair of strings $x, y \in L^2$, where $|x|=|y|$, $x$ may be transformed into $y$ by a sequence of single symbol in-place replacements, so that ...
3
votes
0answers
36 views

What is example of Kahr formula $[\forall\exists\forall, (\omega, 1), (0)]$ and what to do if such undecidable formula is encountered in practice?

There are mentioned many classes of undecidable formulas in the book "The Classical decision problem" http://www.springer.com/la/book/9783540423249. Kahr formulae is one class of undecidable formuls ...
2
votes
0answers
46 views

An approximation variant of the halting problem

It always has been bugging me that we (humans) know pretty easily when most programs we write halt or not, but the halting problem is still undecidable. I have just thought of a variant approximation-...
2
votes
0answers
46 views

Does Rice's theorem apply to sequential logic circuits?

I am wondering if Rice's theorem (or something similar to that) applies also to sequential circuits. I.e. given any finite sequential circuit, can there be an algorithm that can formally verify any ...
2
votes
0answers
96 views

Decide whether a polynomial has a root

Let $A$ be a ring such that all elements of $A$ are complex computable numbers. I'm interested in knowing whether the decision problem that asks, given $P\in A[X]$, if $P$ has a root in $A$ is ...
2
votes
0answers
29 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 ...
2
votes
0answers
52 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]$. ...
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 $...
2
votes
0answers
46 views

Decidability/recognizability of languages with strings lacking alphabet characters

Suppose that $\Sigma = \{c_1, \dots, c_m\}$ is some finite alphabet and supposing $s \in \Sigma^*$, let $\mathcal{I}_j(s)$ denote the number of instances of character $c_j$ in $s$. Call a string $s$ ...
2
votes
0answers
193 views

How to prove a Language is neither a Computably enumerable nor Co-Computably enumerable?

What would be the general approach for that? And what are the things that generally overlooked while proving such things? For example, I have a Language, L ={e:$L(M_e)$ such that it accepts only 'a ...
1
vote
0answers
23 views

How to reduce $\overline{K} \leq L$, or how to show semi-decidability of a given language?

I'm currently preparing for an exam and I'm having trouble to solve the following Questions. Let $w \in \{0,1\}^*$ and let $L$ be a language defined as follows $$L = \{w \mid \mathsf{time}_{M_w}(x) \...
1
vote
1answer
28 views

Question about Turing and Many-One Reductions

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
1answer
26 views

Complement of equality problem of Turing machine is recognisable or not

Complement of equality problem of Turing machines is unrecognisable or not-recognizable but How?. As per my knowledge it is recognisable if you can decide its accept condition but not Reject and ...
1
vote
0answers
45 views

Undecidability of an Intersection

1)"Given a CFL L and a regular language R, is the intersection of L and R an empty set?" decidable? 2)What if we replace L with the complement of L? Either 1 or 2 is decidable and the other ...
1
vote
0answers
21 views

Is undecidability contained in $PSPACE / o(exp(n))$?

It is not hard to show that $DSPACE(n+1)/2^n$ contains undecidability. But is it possible to make the advice string subexponentially long (while the machine is allowed to have any $poly(n)$ space) ...
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 ...
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 ...
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$ ...
1
vote
0answers
45 views

Is it semidecidable to test whether a Turing decidable language is empty?

I'm not sure how to go about solving this. I tried this: Suppose L is a Turing decidable language. Turing Machine M1 is a decider of L and M2 is a decider of the complement L We construct a TM U ...
1
vote
0answers
93 views

How does a PDA compare two configurations of accepting histories?

In Michael Sipser's book, they prove that ALL_CFG = { G | G is a CFG and L(G) = Σ∗ } is undecidable using accepting computation histories and PDAs. My question is how exactly (with details of ...
1
vote
2answers
539 views

Can I apply Rice's theorem to decide decidability status of these languages?

I came across these languages: A Turing machine prints a specific letter. A Turing machine computes the products of two numbers I was guessing whether I can apply Rice's theorem to decide upon above ...
1
vote
1answer
744 views

Undecidable: $w$ on which a TM M $M$ halts after $\leq w$ steps

The detailed question is: Is there a word $w$ on which a TM M $M$ halts after a maximum of $|w|$ (word length) steps? I highly assume, that this problem is not decidable because in the worst case ...
1
vote
0answers
131 views

Why full Chomsky hierarchy is so detailed, if there are decidable recursive languages?

One can have a look on the Chomsky hierarchy https://en.wikipedia.org/wiki/Chomsky_hierarchy , especially the inset named "Automata theory: formal languages and formal grammars" at the bottom of the ...
1
vote
0answers
92 views

Can a CFG generate an accepting configuration? - or is there a turing-recognizable CFG language that is not decidable

I could not think of a way to concisely write down my question clearly, but I'd like to ask, from Sipser's book, $ALLCFG$ is an undecidable language (where $ALLCFG$ means that $G$ is a $CFG$ that ...
1
vote
1answer
835 views

decidability about intersection of regular language and context free language

Is "Given a CFL L and a regular language R, is intersection of L and R an empty set?" decidable? What if we replace L with the complement of L? One of them is decidable and the other is not. For the ...
1
vote
0answers
174 views

Rice theorem to prove Emptiness problem

Is it possible to use the theorem of Rice to prove that the emptiness problem is undecidable? With the emptiness problem I mean the question if a certain machine doens't accept any input ? If you ...
1
vote
0answers
58 views

A Turing Machine with undecideable Halting Status not relying on Open Problems

Is there any turing machine that it is proovably known to be undecideable, it has to fullfit the following characteristics: Not rely on Open Problems/ Conjectures Should not use the same machine used ...
1
vote
0answers
23 views

Computing shifted fix point in the BSS model

Let $p \colon \mathbb{R}_{\geq 0} \rightarrow \mathbb{R}_{\geq 0}$ be a one-dimensional function that fulfills $p(0)=0$. Moreover, we are given some value $u \in \mathbb{R}_{> 0}$ such that $p$ is ...
1
vote
0answers
75 views

Undecidability of an existential theory

$F[u, u^{-1}]$ is a ring that contains the polynomials in $u$ and $u^{-1}$ with coefficients in the field $F$. Some theorems (from https://math.stackexchange.com/questions/1382120/ft-has-undecidable-...
1
vote
0answers
19 views

Is deciding whether there is a non-constant solution to a functional inequality with polynomial arguments decidable, with 2 variables?

So suppose we have a functional inequality with polynomial arguments in $2$ variables, $\sum_i c_i f(p_i(x,y)) \geq 0$, where $c_i$ are say given integer constants and $p_i$ are given polynomials, say ...
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 ...
0
votes
1answer
41 views

Can a $TM$ decide the binary $PCP-Problem$

I am having a little bit of a hard time distinguish between a $TM$ which accepts a language, and a $TM$ that decides a language. To be more precise: $L_1 = \{<M> \; | \; M$ accepts the 10-PCP $\}...
0
votes
1answer
45 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 ...
0
votes
0answers
51 views

Is the language of Turing Machine encodings decidable is this instance?

I have an exercise question as follows: L is a set of all Turing Machine encodings for which the Turing Machine halts after a number of steps less than or equal to the minimum value among |w| and 1000,...
0
votes
0answers
27 views

Would a "TM starting with a blank tape will ever write a nonblank symbol anywhere before halting" be decidable?

Would a "TM starting with a blank tape will ever write a nonblank symbol anywhere before halting" be undecidable?
0
votes
0answers
19 views

Purpose of Acceptance Problem

I am confused about the purpose/statement of the Acceptance problem: $A_{TM} =\{\langle M\rangle\,s |$ Turing machine $M$ accepts $s\}$ It can be shown that $A_{TM}$ is uncomputable, so we know that, ...
0
votes
1answer
28 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
1answer
45 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 ...
0
votes
0answers
42 views

halting problem vs watchdog

I have a theory that all finite state machines can be monitored by a second turing machine with infinite tape to determine if the state of the first machine was repeated thus reaching the conclusion ...
0
votes
0answers
48 views

Let $f$ be a computable and injective function. Is $f^{-1}$ computable and injective?

So I just started learning about computability, undecidability and Turing machines. And I wonder if: Given a computable and injective function $f$, is $f^{-1}$ also computable and injective? I don't ...
0
votes
2answers
49 views

Is it decidable when a TM M gets another as inputs and checks if it fullfiills certain property?

I was asking myself if it is not possible to decide the language where a TM M gets the Godel number of a TM M' as input and the checks if, let us say, the TM M' has a certain amount of transitions. My ...
0
votes
1answer
313 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 ...
0
votes
0answers
43 views

Show that this language is undecidable

Given the language $K$ $=\{<M> $ where $M$ is a turing machine ( that is on the alphabet {0,1}) and $L(M)$ contains at least one word of form $0^k1^l$ with $k,l\geq 0\}$ I would like to know if ...
0
votes
0answers
252 views

reduction from ALLTM to ETM

I am trying to understand why this "proof" of ETM undecidability is wrong. ALLTM={ < M >|M is a TM, L(M)=∑*} ETM={< M >|M is a TM, L(M)=∅} We know that ALLTM is undecidable, lets ...