# Questions tagged [undecidability]

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

871 questions
Filter by
Sorted by
Tagged with
1 vote
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 ...
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 ...
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 ...
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. ...
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 ...
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 ...
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 ...
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 ...
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 ...
1 vote
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 ...
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 ...
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 ...
26 views

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 ...
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 ...
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 ...
1 vote
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 ...
1 vote
111 views

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 ...
1 vote
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 ...
1 vote
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 ...
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 ...
1 vote
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 ...
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 ...
1 vote
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$ ...
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$ ...