# Questions tagged [undecidability]

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

64 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
42 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 ...
126 views

43 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$ ...
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 ...
105 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 ...
100 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 ...
70 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 ...
58 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 ...
398 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 ...
187 views

Consider a Turing machine $T$ with access to an oracle for a proper, nonempty subset of $A_{TM}$, say $L$. That is, $T$ can query this oracle to check whether some string belongs or doesn't belong to $... 0answers 154 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 ... 0answers 55 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 ... 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 ... 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-... 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_iare given polynomials, say ... 0answers 17 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:=\... 0answers 23 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 ... 0answers 24 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 ... 0answers 7 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 ... 0answers 31 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 ... 0answers 19 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 ... 0answers 28 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 ... 0answers 53 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 ... 0answers 21 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? ... 1answer 56 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 ... 1answer 67 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 ... 0answers 57 views ### What Makes A TM undecidable (using Recursion Theorem) PROOF :We assume that Turing machine H decides ATM for the purpose of obtaining a contradiction. We construct the following machine B. B =“On input w: Obtain, via the recursion theorem, ... 0answers 33 views ### I've proven my language undecidable what is left to prove it Turing equivalent? Let us say that I have a computation model A. Let us also say that I have shown that A can be simulated by a Turing machine. I have not been able to prove that A can simulate a Turing machine. ... 0answers 42 views ### Is reduction from A_TM to EQ_TM possible to prove EQ_TM is undecidable? \begin{align} EQ_{\mathrm{TM}} &= {\{ \langle M,N\rangle : L(M)=L(N) \}}\\ A_{\mathrm{TM}} &= {\{ \langle M,w\rangle : \textrm{TM M accepts w}\}} \end{align} I can do it using E_{\mathrm{... 0answers 28 views ### Is the proof for the undecidability of A_{TM} still valid if we change certain parts? i have a question based on a question i saw exists on the site, but with wrong information in it and no answer there, so i am reposting it with valid information(cited wrong from the book). on page ... 0answers 94 views ### Proving language K is undecidable using the diagonalization method I have a problem proving the following properties of given language K: K = \{< M > | M\ accepts < M >\} I am trying to prove that language K is Turing-recognizable but undecidable ... 0answers 36 views ### Effects of changes in the proof that A_{\text{TM}} is undecidable In the proof that A_{\text{TM}} undecidable we use the following machine: D = On input \langle M, w \rangle: Simulate M on input w. If M ever enters its accept state, accept. ... 2answers 106 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 (... 1answer 158 views ### A language which is neither r.e. nor co-r.e First, considerL_\exists=\{\langle M\rangle \mid M \text{ is a Turing machine and accepts some input}\}$$is RE. I tried to construct a Turing machine: ... 0answers 28 views ### A set that is not recursively enumerable and not (K'≤ A) Is there a set A such that it's not recursively enumerable and not(K'≤ A) ? where K' is complement of K= {n| φ n (n) halts} Thanks! 0answers 57 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? 0answers 103 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 ... 0answers 32 views ### How to prove that for a decidable problem the problem and the compliment of the problem are semi-decidable? Given a decidable problem, how would I go about proofing that the problem and the complement of the problem have to be semi-decidable? 0answers 104 views ### Why is set of Turing machine set DD = {⟨M⟩ | ⟨M⟩⟨M⟩ not in L(M)} not decidable? To prove that the set \mathrm{DIAG} = \{\langle M\rangle \mid \langle M\rangle \notin L(M)\} is not decidable, we can assume, to the contrary, that there is a Turing Machine M such that L(M) = \... 0answers 295 views ### Decidability of intersection of two languages of same type Given two context-sensitive languages, L_1 and L_2 is the problem of "whether L_1 \cap L_2 also belongs to CSL" decidable? I have the same question for the case when L_1 and L_2 belongs to ... 0answers 40 views ### Is the language below not decidable , if yes , it is then R.E ? I am given a Turing machine M as input and i have to find out if this language below decidable and if not is it then in this case recursively enumerable .$$L=\\\{<M> \mid \text{ is ... 0answers 135 views ### Is {< M >| L(M) ∩ (ab)∗ is infinite} in D, SD/D, or not in SD? Are these languages in D, SD/D, or not in SD? $$L_1 = \{\langle M \rangle\mid L(M)\cap (ab)^*\text{ is infinite}\}$$ I kind of understand decidability and undecidability problems, but the "\cap(ab)^...
$L_1=\{ ⟨M⟩ ∣M$ takes at least 2016 steps on some input$\}$ the answer says $L_1$ is recursive. I am stuck at one point and i am wasting my time on it here for $L_1$ if we are given a set of to see ...
We define a language $L$: $\qquad L=\{\langle M,w,k \rangle \mid M(w) \text{ reaches configuration } \alpha q \beta \text{ with } |\alpha \beta| \geq k \}$ with $M$ Turing machines with state set $Q$...