Linked Questions

27
votes
7answers
6k 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. ...
43
votes
2answers
15k 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 ...
9
votes
4answers
3k 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 ...
30
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 ...
4
votes
2answers
4k 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?...
7
votes
4answers
724 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
774 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
4k 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(...
0
votes
2answers
1k 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 ...
0
votes
2answers
2k 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 ...
1
vote
1answer
383 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
138 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 ...
2
votes
2answers
291 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
votes
1answer
495 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:\...
1
vote
1answer
262 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 ...

15 30 50 per page