Linked Questions

7
votes
1answer
3k views

Why can't we solve the Halting Problem by using Artificial Intelligence? [duplicate]

Yesterday I was reading about Computability and they mention the Halting Problem. It got stuck in mind all day until I remember that some weeks ago, when learning Java, the IDE (Netbeans) show me a ...
2
votes
2answers
5k views

Why is the halting problem unsolvable by a turing machine? [duplicate]

So my knowledge of CS is amateurish at best but to me, logically, it seems like the halting problem is solvable. So any human can determine if a problem halts with rigorous inspection, so why can't a ...
2
votes
1answer
6k views

Rice Theorem - What is non-trivial property? [duplicate]

Every nontrivial property of the recursively enumerable languages is undecidable. What exactly is nontrivial property?
1
vote
2answers
597 views

Is emptiness of the intersection of the languages of two TMs decidable? [duplicate]

Let $\qquad \mathrm{DISJOINT} = \{ \langle M_1,M_2 \rangle : M_1, M_2 \text{ are TMs and } L(M_1) \cap L(M_2) = \emptyset\}$. How do I know if this language is decidable or not? And How do I prove ...
1
vote
1answer
900 views

Proving a function is uncomputable [duplicate]

I am trying to solve the following problem: For each Turing machine $M_k$ and each string $x$ in $\{$0,1$\}$$^\ast$ let $time_k(x)$ = $\{$the number of steps executed by $M_k(x)$ if $M_k(x)$$\...
0
votes
0answers
194 views

Is it decidable whether a TM accepts more than one word? [duplicate]

Is the following language: $\qquad\displaystyle L= \{\langle M\rangle \mid M \text{ is a TM }, |L(M)|>1\}$ Turing-decidable? I think it isn't, because if a Turing machine T can decide L, ...
0
votes
1answer
95 views

Reference for an undecidability proof [duplicate]

I'm searching for a reference of an undecidability proof that is as simple as possible and starts "from scratch". With "from scratch" I mean that it does not use some other undecidable problem to ...
0
votes
0answers
82 views

Prove whether this language is (partially) decidable [duplicate]

I'm currently working on a few turing machine exercises and I can't understand how I can prove whether the below is at least partially decidable: $\{M \mid L(M) = \{x \mid |x| = 10\}\;\}$ where $|x|$ ...
0
votes
1answer
45 views

How do I prove no algorithm exists for a given problem? [duplicate]

Is there a general framework for showing that a problem has no algorithm? For example, to show that two problems are equally as hard to each other, we use reduction. One example of where this was ...
0
votes
0answers
46 views

Proving that $L=\{ \langle M \rangle \colon L(M)=L(M)^R \}$ is undecidable [duplicate]

I'm trying to show that $L=\{ \langle M \rangle \colon L(M)=L(M)^R\}$ is undecidable, but I don't even know where to begin. Google wasn't much of a help, maybe because it's hard describing the ...
0
votes
0answers
40 views

Recursive set - How to show a language is undecidable [duplicate]

I am currently working on the following task: A language L = {< M> | M(x) = x^2} is given. Now I need to show, that this language is not decidable. By the way, < M> is the Gödel number But ...
0
votes
0answers
27 views

How to proof a function is not computale [duplicate]

I wish to undestand how to proof a function is/is not computable. I found this example online (without solution) beacuse I was thinking was easy to understand, but I am stuck in understanding how to ...
0
votes
0answers
27 views

How to prove that a language of machines accepting a fixed string is decideable? [duplicate]

Is L = $\{\langle M,w\rangle \mid \text{$M$ accepts string epsilon or string $w$, or both} \}$ decidable? I attempted to use Rice's Theorem for this question to prove that it is undecidable. Is my ...
0
votes
0answers
20 views

Show that the set of TMs that can write z is undecidable [duplicate]

I want to show that $\qquad L = \{\langle M \rangle \mid \text{TM $M$ will write a $z$ to the tape at some point for some input}\}$ is undecidable. I'm really not sure how to show this is ...
38
votes
2answers
7k 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". ...

15 30 50 per page