Questions tagged [undecidability]

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

Filter by
Sorted by
Tagged with
1 vote
0 answers
35 views

Help me verify my proof that FINITE is undecidable

Is my proof that FINIT is undecidable correct? FINITE= { ⟨M⟩ | M is a Turing machine that accepts only finitely many strings } is undecidable. Answer: To prove this we can use reduce to Halting ...
Sachihiro's user avatar
  • 111
6 votes
2 answers
2k views

What does it mean to prove the halting problem is undecidable "using arithmetization"?

In version gamma of the ACM/IEEE/AAAI Computer Science Curricula 2023, on page 50, one of the illustrative learning outcomes for the "Computational Models and Formal Languages" section of ...
user164282's user avatar
0 votes
0 answers
22 views

If we have two TMs D1 and D2 and the languages of the TMs L(D1) != L(D2), then is this problem decidable/recognizable? [duplicate]

We know that in the case where, L(D1) = L(D2), the problem is undecidable. But what happens when the languages are not equal? I would assume it's still undecidable, but is it recognizable? And how ...
Luis Ramirez's user avatar
0 votes
1 answer
48 views

A program that solves the Halting Problem for programs with N states

My question relates to the conclusions drawn from the Halting Problem. I understand that the Halting Problem proves that no program H(P,i) exists that determines if P(i) halts or not for P in general. ...
Vincenzo Buselli's user avatar
-1 votes
2 answers
49 views

Show that the language is undecidable

Consider the language L = {< M >| M accepts iff input length is divisible by 3}. I'm supposed to use reduction to show that the language is undecidable. I tried proving it but didn't know what ...
berlin23's user avatar
-6 votes
1 answer
55 views

Is ChatGPT wrong about the definition of unrecognizable and undecidable languages?

I asked ChatGPT to give me the difference between unrecognizable and undecidable languages, and this what it gave me: Unrecognizable languages can be accepted by a Turing machine, but the machine may ...
Aland Ameer's user avatar
5 votes
7 answers
3k views

What are the conditions necessary for a programming language to have no undefined behavior?

For context, yesterday I posted Does the first incompleteness theorem imply that any Turing complete programming language must have undefined behavior?. Part of what prompted me to ask that question ...
Mikayla Eckel Cifrese's user avatar
0 votes
3 answers
91 views

Why can't we use computation history to detect looping of a Turing machine on a given input?

First of all, obviously there is a flaw in my logic and I just want to know what it is. So here is my idea: Given a TM M and an input string ω, simulate M on ω on another TM S. For every change of ...
Aland Ameer's user avatar
0 votes
2 answers
61 views

Infinite Recursion as the Intuitive Foundation for the Halting Undecidability Proof

all, I was wondering if my intuitive understanding of why the halting problem is undecidable is actually correct? TLDR: Halting problem is undecidable because it leads to infinite recursion and never ...
boinka's user avatar
  • 1
1 vote
1 answer
163 views

What could $P = NP$ imply about arbitrary Turing machines?

My question: What $P \not= NP$ or $P = NP$ could imply about arbitrary Turing machines and arbitrary computations? I assume that a partial and incomplete, but objective answer to this question exists ...
Axid Ubish's user avatar
3 votes
0 answers
185 views

Does this paper by Patrick Cousot describe an undecidable method for model checking?

All of the discussion is in the context of this paper. I think that the whole procedure that the paper describes is not decidable, because if we can have an algorithm for it, then we can solve halting ...
Senmorta's user avatar
0 votes
1 answer
411 views

TMs can decide whether or not a string is a Palindrome, yet, the language called PALINDROMES is undecidable - why?

I came across this language, where M denotes a Turing Machine: PALINDROMES $:= \{M \mid M \text{ accepts strings which are palindromes}\}.$ It is proven to undecidable. And, I know one can construct a ...
HaferFlockenPengu's user avatar
0 votes
0 answers
26 views

$FINITE_{TM}$ is not Turing-reducible to $A_{MT}$

$FINITE_{TM} = \{\langle M \rangle\mid M\text{ is a TM and }L(M)\text{ is finite}\}$ $A_{MT} = \{\langle M,w \rangle \mid M\text{ is a TM and }M\text{ accepts }w\}$ I'm trying to prove that $FINITE_{...
Laurus Laurus's user avatar
1 vote
1 answer
39 views

Reformulating the Given Conditions in Decidability Problems

I came across the following question: Given two context-free languages $L_1$ and $L_2$ is it decidable whether $L_1 - L_2 = \emptyset$ ? The problem $ALL_{\text{CFG}}$ that states: Given a CFG $G$ ...
RookieCookie's user avatar
0 votes
0 answers
46 views

Is the $Even - Halt$ problem decidable?

Is the language: $$L = \{\ \langle M \rangle \ |\text{ There is an input $w$ such that M performs even number of steps before M halts on $w$} \}$$ They way I approached the problem the was the ...
Giorgos - Marios Patelis's user avatar
1 vote
1 answer
84 views

Is the problem of Proper Subset of decidable languages decidable?

Given 2 recursive - decidable languages $L_1$ and $L_2$ is the problem $L_1 \subset L_2$ solvable - decidable? Since both $L_1$ and $L_2$ are recursive - decidable there exist Turing Machines say $M_1$...
RookieCookie's user avatar
0 votes
0 answers
23 views

Question regarding rice theorem

this is a question I got from a test that we had before Let there be X, a subgroup of languages above $\Sigma $ such that X isn't empty nor all of the langauges in $\Sigma $ we need to say if the ...
elay dadnon's user avatar
0 votes
0 answers
39 views

How to prove $\{\langle M\rangle: L(M)=\emptyset\}$ is undecidable?

Consider the language $$E_{T M}=\{\langle M\rangle: L(M)=\emptyset\}.$$ Prove that $E_{T M} \in \text{coRE} \backslash\text{R}.$ I proved that $$E_{T M} \in\text{coRE}$$ using Turing machine I built ...
user1701057's user avatar
0 votes
0 answers
19 views

proving or disproving a reduction from $R \leq P(Σ^*) \backslash RE$

I need to prove or disprove that for all languages in $R$ there is a reduction to all languages in $P(Σ^*)\backslash RE$. And I'm having trouble to figuring out the solution, especially with dealing ...
yoav's user avatar
  • 1
0 votes
0 answers
47 views

Undecidability of syntactic properties

Rice's theorem comments on the undesirability of non-trivial semantic properties, however there are syntactic properties that are undecidable as well, such as the "useless" states problem ...
Alan Whitteaker's user avatar
-2 votes
1 answer
60 views

EPSILON(CFG) = {<G,H> | G and H are CFGs where the concatenation is epsilon. is this language Turing-recognizable?

It is given that the language is not decidable. Is this language Turing-recognizable?
Tomer Mor's user avatar
0 votes
1 answer
225 views

Modify Turing’s proof of the undecidability of the halting problem

Modify Turing’s proof of the undecidability of the halting problem to show there is no Turing machine P with the following two properties: For all Turing machines M, if M() accepts then P(⟨M⟩) ...
staz6's user avatar
  • 25
0 votes
1 answer
43 views

Is there a maximal set of programs that terminate?

It seems useful to characterize terminating programs. While trying to formulate that as a well-defined question I was wondering about the following problem: Is there a maximal decidable set of ...
timgo's user avatar
  • 103
0 votes
0 answers
28 views

How can decidability/semi-decidability/undecidability have impact on REAL life applications/examples?

How decidability/semi-decidability/undecidability has impact on REAL life applications/examples? I understand that it can be used for implementation of various algorithms but what else?
Arthemoon's user avatar
  • 141
0 votes
1 answer
168 views

If a language is undecidable, then its complementary language must also be undecidable?

Reference from here If a Language is Non-Recognizable then what about its complement? There exist complementary languages of unrecognizable languages that are recognizable, and there exist ...
lz9866's user avatar
  • 305
0 votes
1 answer
46 views

Unrecognizable languages must be undecidable?

A decidable language must be recognizable. Unrecognizable languages must be undecidable? I want to know more about the relation of undecidability and unrecognizability
lz9866's user avatar
  • 305
0 votes
1 answer
34 views

If the complementary language of an recognizable language is a non-recognizable language, is the recognizable language a non-decidable language?

The complementary language of a recognizable undecidable language is not recognizable. If the complementary language of an recognizable language is a non-recognizable language, is the recognizable ...
lz9866's user avatar
  • 305
1 vote
0 answers
24 views

Reduction from $\mathsf{ALL}_{\mathsf{TM}}$ to it's complement

I'd like to know if there's a reduction $\mathsf{ALL}_{\mathsf{TM}}\leq_{m}\overline{\mathsf{ALL}_{\mathsf{TM}}}$ where of course $\mathsf{ALL}_{\mathsf{TM}}=\left\{ \left\langle M\right\rangle \mid\...
Ariel Yael's user avatar
2 votes
2 answers
120 views

Proving that there is no solution to the PCP problem using induction

I'm studying for the Algorithms and Computability course. I have encountered a problem that I cannot solve and cannot find any materials to help me solve it. It's the following PCP problem: We have ...
Miszka's user avatar
  • 23
0 votes
2 answers
82 views

Decidability of the minimum number of states a Turing Machine needs to accept a language

I'm reading some old notes from a course on Turing Machines and I've bumped into the following question: Is the following language decidable? The language formed by the set of all Turing Machines ...
user2891462's user avatar
0 votes
1 answer
63 views

Decidable or Not: Set of all Turing Machines M that on input w uses all states of M

Show that the following language or problem is not recursive: $$ L=\{\langle M,w\rangle\mid \text{computation of TM } M \text{ on input } w \text{ uses all states of } M\} $$ I was trying to prove it ...
enouema's user avatar
1 vote
2 answers
68 views

What machines are required to solve the emptiness of regular and context-free langauges?

Consider the language definition: $L = \{<M>| M$ is a DFA and $M$ accepts some string of the form $ww^{r}$ for some $w\in \Sigma^{*}\}$ The language $L$ is : A) Regular B) Context-free but not ...
Arun Madhav's user avatar
1 vote
1 answer
111 views

Is the equivalence problem of a CFG and a FSM decidable?

I have the following problem: Given a context-free grammar $\mathcal{G}$ and a finite state automaton $\mathcal{A}$, where both are over the alphabet $\Sigma=\{0, 1\}$. Is it decidable whether $L(\...
sockaddr's user avatar
0 votes
0 answers
63 views

How to prove by reduction this (acceptance?) problem

At school I was assigned this example: Prove by the reduction method that it is undecidable whether for a given Turing machine M with the alphabet {a, b, _} holds aabb ∈ L(M). I think it's acceptance ...
ZlyVlk's user avatar
  • 1
0 votes
1 answer
53 views

What characteristics would a PDA $A$ where $L(A)=\Sigma^*$ have?

I understand that the problem of whether a PDA accepts all strings is undecidable. However that doesn't mean such PDAs exist. To start, I'm working under the assumption that a PDA must read it's ...
Gabe Kelly's user avatar
0 votes
0 answers
29 views

Recursive language sandwiched between two non-RE languages

I need to find three languages $L_1,L_2,L_3$ that satisfy: $L_1 \subseteq L_2 \subseteq L_3$. $L_1,L_3 \notin RE$. $L_2 \in R$. I can't think of any other language that is not RE, except for $$L_d = ...
CSstudent's user avatar
0 votes
5 answers
2k views

Does contradiction definitively prove nonexistence

It is common to have proofs that use contradiction to show that some language is undecidable in computability theory. An example proof can be seen in 4.2 Undecidability “Introduction to the Theory of ...
Dereference's user avatar
0 votes
1 answer
233 views

Is the infinite union of decidable languages decidable?

I am currently struggling with figuring out the following problem: Given decidable languages L1, L2, L3, L4, ... Is the infinite union of Languages L1, ...... decidable? I have an intution that it is ...
Druckermann's user avatar
0 votes
1 answer
54 views

Show that Lu is m-reducible to the language L = {⟨M, x⟩ | M(x) terminates with an empty tape}

Question: Given a language L, L = {⟨M, x⟩ | M(x) terminates with an empty tape}, show that Lu is m-reducible to L by finding a computable function f: Σ* -> Σ*, where for every w, w ∈ Lu if and only ...
Jane's user avatar
  • 1
0 votes
0 answers
39 views

Prove that a language does not many one reduce to its complement

I am trying to prove that an undecidable language $L$ is not many one reducible to its complement. The problem goes as follows: Formally prove that $L \not\leq_m \overline{L}$ for any undecidable $L$....
jamess's user avatar
  • 1
10 votes
4 answers
2k views

Probabilistic methods for undecidable problem

An undecidable problem is a decision problem proven to be impossible to construct an algorithm that always leads to a correct yes-or-no answer. I wonder if there are examples of probabilistic ...
Student's user avatar
  • 219
0 votes
1 answer
53 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 $...
pod's user avatar
  • 117
0 votes
0 answers
113 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 ...
Ronald's user avatar
  • 89
1 vote
1 answer
81 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 ...
T. Rex's user avatar
  • 121
1 vote
1 answer
47 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 ...
Niklas Rosencrantz's user avatar
2 votes
1 answer
133 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 ...
Ronald's user avatar
  • 89
1 vote
1 answer
169 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 ...
Fred Jefferson's user avatar
0 votes
1 answer
637 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 ...
ArithEgo's user avatar
1 vote
1 answer
125 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$ ...
Fred Jefferson's user avatar
2 votes
1 answer
261 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$ ...
Xiobiq's user avatar
  • 161

1
2 3 4 5
18