# Questions tagged [undecidability]

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

750 questions
Filter by
Sorted by
Tagged with
1answer
722 views

### computability - decidability of a prefix language

For any language $L$ over $\{0,1\}^*$, a language $L'$ can be defined as $\{ a | ab \in L \text{ for some } b \in \{0,1\}^* \}$. If $L$ is decidable, is $L'$ decidable? I think that $L'$ should be ...
2answers
288 views

### Is this a correct decider?

We are given the following language B = {$<M,i>$ : M is a turing machine and $i \in \mathcal{N}$ and M accepts some string in atmost $i$ steps } Is language B decidable ? As per a hint from ...
2answers
328 views

1answer
2k views

### Decision problem and algorithm

I was reading about decision problem. I understand that decision problem tell yes/no answer for an input. The decision is based on a decision procedure also called an algorithm. The wikipedia says ...
2answers
439 views

### Is the undecidable function $UC$ well-defined for proving the undecidability of Halting Problem?

I am new to Computability Theory and find it is both amazing and confusing. Specifically, it is difficult for me to get through the undecidability of the well-known Halting Problem. Halting ...
2answers
1k views

### Is undecidable(complement of R) a subset of NP-hard?

Is there an undecidable problem which is not NP-hard?
1answer
457 views

### Is the intersection of two regular languages regular?

Trivially decidable problem is one in which the problem is a known property of the language/grammar. So intersection of two regular languages is regular should be trivially decidable? But it is given ...
3answers
2k views

### Undecidability of the following language

So we can prove that the language say $A = \{ \langle M,w \rangle \mid \text{M is TM that accepts } w^R \text{ whenever it accepts } w \}$ is undecidable by assuming it is decidable and use that to ...
1answer
823 views

### Solvability of Turing Machines

I'm preparing for an exam, and on a sample one provided (without solutions), we have this question: Is the following solvable or non-solvable: Given a turing machine $T$, does it accept a word of even ...
1answer
147 views

1answer
160 views

4answers
1k views

### What approaches are most useful when proving uncomputability of a given function?

I'd like to understand what approaches should one adopt when deciding/proving that a given function F is uncomputable, by any Turing Machine (TM). The ones I've tried so far are as follows: Reduction,...
1answer
18k views

### What is the difference between halting, accepting, and deciding in the context of Turing machines?

Does accepting mean that the TM will read and recognize a char from the cell it's currently reading from? And is it the case that a TM halts iff the input is decidable?
2answers
7k views

### Is it decidable whether a TM reaches some position on the tape?

I have these questions from an old exam I'm trying to solve. For each problem, the input is an encoding of some Turing machine $M$. For an integer $c>1$, and the following three problems: ...
1answer
234 views

1answer
3k views

### Examples of undecidable problems whose intersection is decidable

I know that given two problems are undecidable it does not follow that their intersection must be undecidable. For example, take a property of languages $P$ such that it is undecidable whether the ...
1answer
838 views

### Showing that the set of TMs which visit the starting state twice on the empty input is undecidable

I'm trying to prove that $L_1=\{\langle M\rangle \mid M \text{ is a Turing machine and visits } q_0 \text{ at least twice on } \varepsilon\} \notin R$. I'm not sure whether to reduce the halting ...
2answers
8k views

### Perplexed by Rice's theorem

Summary: According to Rice's theorem, everything is impossible. And yet, I do this supposedly impossible stuff all the time! Of course, Rice's theorem doesn't simply say "everything is impossible". ...
2answers
200 views

### Semi-decidable problems with linear bound

Take a semi-decidable problem and an algorithm that finds the positive answer in finite time. The run-time of the algorithm, restricted to inputs with a positive answer, cannot be bounded by a ...
2answers
257 views

### Why absence of surjection with the power set is not enough to prove the existence of an undecidable language?

From this statement As there is no surjection from $\mathbb{N}$ onto $\mathcal{P}(\mathbb{N})$, thus there must exist an undecidable language. I would like to understand why similar reasoning ...
4answers
5k views

5answers
1k views

### Is it possible to solve the halting problem if you have a constrained or a predictable input?

The halting problem cannot be solved in the general case. It is possible to come up with defined rules that restrict allowed inputs and can the halting problem be solved for that special case? For ...
2answers
1k views

### Is there a “natural” undecidable language?

Is there any "natural" language which is undecidable? by "natural" I mean a language defined directly by properties of strings, and not via machines and their equivalent. In other words, if the ...
1answer
506 views

### Ratio of decidable problems

Consider decision problems stated in some “reasonable” formal language. Let's say formulae in higher-order Peano arithmetic with one free variable as a frame of reference, but I'm equally interested ...
4answers
923 views

### Is this finite graph problem decidable? What factors make a problem decidable?

I want to know if the following problem is decidable and how to find out. Every problem I see I can say "yes" or "no" to it, so are most problems and algorithms decidable except a few (which is ...
1answer
2k views

### Rice's theorem for non-semantic properties

Rice's theorem tell us that the only semantic properties of Turing Machines (i.e. the properties of the function computed by the machine) that we can decide are the two trivial properties (i.e. always ...