Questions tagged [undecidability]

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

83 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
4
votes
0answers
43 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
132 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
58 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
264 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
103 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
54 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
34 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
62 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
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 ...
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]$. ...
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
44 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
164 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
37 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
38 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
19 views

Many-one reductions between the set of true sentences and a particular arithmetical set

Never used this site before so not sure the best way to get help. However, I've been looking at many-one reductions in relations to sentences in logic. Let TH(N) = {ϕ : ϕ is a first order sentence ...
1
vote
0answers
19 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
52 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
236 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
255 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
89 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
74 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
0answers
538 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
161 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
74 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
100 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
0answers
29 views

How would I prove that nondeterministic Turing machines are undecidable?

How would I go about proving that the language: $$A_{NTM }= \{\langle N, w\rangle | N \text{ is a nondeterministic TM and } N \text{ accepts }w\}$$ is undecidable? I looked at the proof for $A_{TM}$ ...
0
votes
0answers
49 views

Undecidability of the language of PDAs that accept some ww

I'm trying to solve problem 5.33 from Sipser's Introduction to the Theory of Computation, "Consider the problem of determining whether a PDA accepts some string of the form $\{ww|w\in \{0,1\}^∗\}$...
0
votes
0answers
30 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 ...
0
votes
1answer
38 views

Are all Recursively Enumerable languages which are not Recursive also Undecidable?

Knowing that all Recursive languanges are Decidable and All Not R.E. Languages are Undecidable (correct me if I am wrong), Are all languages which are R.E. but not Recursive also Undecidable? R.E. ==&...
0
votes
0answers
24 views

TM for Language With a Specific Cardinality

I'm curious about how to build TM that decide and recognize languages defined by cardinality. For example, with the language $L_1$ = $\{w \in \{0,1\}^* | |w| = 1\}$ this is the language with a single ...
0
votes
0answers
36 views

Is the undecidability of a given problem undecidable?

Given an input problem P, can you construct an algorithm A to compute whether or not P is decidable or undecidable? In other words, is the undecidabiliy of a problem undecidable? My initial guess is ...
0
votes
1answer
38 views

Mapping reduction from $A_{TM}$ to $INFINITE_{TM}$ same as to $ALL_{TM}$?

I was trying to solve a problem with a mapping reduction from $A_{TM}$ to $INFINITE_{TM}$, and came across a solution that was 100% identical to another solution I saw for $A_{TM} \leq_M ALL_{TM}$. ...
0
votes
0answers
31 views

Is it decidable to know the number of positions used by a Turing machine for a fixed input?

I'm having trouble proving if the following language is recursive, recursively enumerable, or not r.e. at all: the set of all encodings of Turing machines $M$ such that the number of positions in the ...
0
votes
0answers
38 views

A Turing machine for which it is impossible to predict whether it halts or not on a fixed input

The halting problem is undecidable, i.e. $\not \exists$ $M$ Turing machine s.t. for every $(M_0,w_0)$ input where $M$ is the description of a Turing machine and $w_0$ is an input word, the output of $...
0
votes
0answers
27 views

Find decidable sets such that $A$ reduces to $B$ but not vice versa

I am stuck in this problem, so any help is appreciated. The problem asks to show that there exists decidable sets $A$ and $B$ such that $A \leq_{m}^{p} B$ but $B \not \leq_{m}^{p} A$, and that $A$, $B$...
0
votes
0answers
30 views

Can you apply Rice's Theorem on the following languages? Are they decidable?

Can you apply Rice's Theorem on the following languages? Are they decidable? $$L_1:=\{v\mid v \text{ is the Code of a TM } M_v \text{ and } M_v \text{ has an even number of states.}\}$$ $$L_2:=\{v\mid ...
0
votes
0answers
29 views

Is it decidable whether Turing Machine never scans any tape cell more than once when started with given string

The problem: Is it decidable that the set of pairs $(M,w)$ such that TM $M$, started with input $w$, never scans any tape cell more than once. How can I easily prove above to be decidable. I found ...
0
votes
0answers
33 views

reduction: L1’s decidability is unknown and L2 is undecidable

About this question: Reductions can be tricky to get the hang of, and you want to avoid “going the wrong way” with them. In which of these scenarios does L1 ≤m L2 provide useful information (and ...
0
votes
0answers
15 views

Is it possible to write down every Prolog program+query as the sequent in the sequent calculus?

Prolog program P is set of Horn (definite) clauses, effectively it is the conjunction of implicational formulas. I guess that every Prolog program P with some query Q can be written as ...
0
votes
0answers
55 views

Reducing universal language to language of palindromes

I am trying to understand proof for proving language of all palindromes is undecidable from these slides. It tried to reduce universal language to language of all palindromes on alphabet. The two ...
0
votes
0answers
23 views

Correct Turing machine representation for Rice Theorem proof

Consider the language L1. From Rice Theorem I know L1 is not decidable (i.e. undecidable). L1 = { R(M) | R(M) is a TM and 1011 ∈ L(M)} For example if I want to represent by diagram a TM $M_1$ ...
0
votes
0answers
33 views

A TM that doesn't decide Σ*, and a TM that doesn't decide the empty set?

I was wondering if it was possible to create a TM that semi-decides (but doesn't decide) either of the following two languages: $\emptyset$ $\Sigma^{*}$ I assume for 2, a one-state TM that just ...
0
votes
0answers
57 views

Is the language of turing machines, which return epsilon on its own encoding, decidable?

Is the language $\{ \langle M\rangle | f(\langle M\rangle)=\epsilon\}$ decidable? $f()$ means, that the turing machine returns $\epsilon$ on its own encoding and $\langle M\rangle$ stands for the ...
0
votes
0answers
22 views

Is the language $L$=$\{<D_1,D_2> | D_1,D_2$ are DFAs over $\{0,1\}$ and $L(D_1) \subseteq L(D_2)\}$ decidable?

I came up with an algorithm to decide this language, but not sure if it is correct? ...
0
votes
1answer
69 views

Is decidability closed under the mapping f where f(a)=f(b)=0 and f(c)=1?

Consider the function $f$ that maps strings over $\{a, b, c\}$ to strings over $\{0, 1\}$ by replacing each $a$ by 0, each $b$ by 0, and each $c$ by 1. For example $f(cabbc) = 10001$. The function $f$ ...
0
votes
2answers
118 views

Decidable questions of undecidable problems

Even if there is no general algorithm to decide if any program will halt, but there could be properties or meta-questions about the programs that is decidable. For example, given program $A$ and a ...