Linked Questions

32
votes
7answers
9k views

What are the simplest examples of programs that we do not know whether they terminate?

The halting problem states there is no algorithm that will determine if a given program halts. As a consequence, there should be programs about which we can not tell whether they terminate or not. ...
45
votes
2answers
19k views

How to show that a function is not computable?

I know that there exist a Turing Machine, if a function is computable. Then how to show that the function is not computable or there aren't any Turing Machine for that. Is there anything like a ...
10
votes
4answers
4k views

The bounded halting problem is decidable. Why doesn't this conflict with Rice's theorem?

One statement of Rice's theorem is given on page 35 of "Computational Complexity: a Modern Approach" (Arora-Barak): A partial function from $\{0,1\}^*$ to $\{0,1\}^*$ is a function that is not ...
5
votes
2answers
5k views

What's a trivial property?

I have to show a property P is trivial. This problem has to do with Rice's Theorem, which I do not completely understand. Can someone explain the difference between trivial and non-trivial properties?...
31
votes
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 ...
9
votes
4answers
939 views

Implications of Rice's theorem

Every time I think I get what Rice's theorem means, I find a counterexample to confuse myself. Maybe someone can tell me where I'm thinking wrong. Lets take some non-trivial property of the set of ...
6
votes
2answers
1k views

Are these sets of indices also index sets?

An index set is a set of all indices of some family of computably enumerable sets. It is known that the empty set is an index set and that $K = \{e \mid e \in W_e\}$ is not an index set. The ...
2
votes
1answer
5k views

Use Rice's theorem to show that the language of optimisable Turing machines is undecidable

I have an assignment to do and I'm quite stuck with the following question : Use Rice's theorem to show that $ \qquad L' = \{ \langle M \rangle \mid \; (\exists \text{ TM } M') \; [ L(M') = L(M) \...
0
votes
2answers
3k views

How do I prove that a Turing Machine that accepts a string w in an even number of steps is not decidable?

Let a language A = {(M,w) : M is a TM and w is a string such that w is accepted by M in an even number of steps}. How can I prove that this is undecidable? I have considered trying to build the ATM ...
0
votes
2answers
2k views

Prove the halting problem is undecidable using Rice's theorem

Is it possible to prove that the Halting problem is undecidable using Rice's theorem? Here's what I've tried and failed: We want to reduce Rice's Theorem (decide if a language has the nontrivial ...
2
votes
2answers
676 views

Does rice theorem applies to languages only or does it apply to machines as well?

Rice theorem says that any non trivial property of a language recognized by a Turing Machine is undecidable. Now does this theorem applies to machines as well since we can define a language ...
1
vote
1answer
516 views

Is the set of Gödel numbers of computable constant functions recursively enumerable?

I've been working on the following exercise: $S = \{ x | f_x \text{ is constant} \}$. Is $S$ recursively enumerable? Here, $fx$ is the function computed by the $\text{x-th TM}$. So it is a ...
-1
votes
2answers
154 views

Does Rice theorem imply that it is not possible to find out the absolute optimum of a physical process?

One of my friends works for a big oil rafinery. He's in charge of optimising the inputs (volumes, maximum price to pay for crude oil etc.) given a profit. He's telling me there are heuristic ways to ...
1
vote
1answer
362 views

Proving that context-freeness of $L(M)$ is not semi-decidable using Rice's theorem

This is a question from an exam I did today: Given $M$, a turing machine, we need to decide the following: 1) $M$ halts on every input 2) The language of $M$ is CFL My question is, can I ...
-1
votes
1answer
571 views

Use Rice's theorem to prove the following is undecidable

Given the language $L=\{\alpha \mid M_{\alpha}(x)=x^3$ for all $x\in\{0,1\}^*\}$. Prove using Rice's theorem that $L$ is undecidable. Rice's theorem: Let $P$ be a set of all computable functions $f:\...

15 30 50 per page