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
4k 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 ...
1
vote
1answer
5k 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
1answer
773 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)$$\...
1
vote
2answers
414 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 ...
0
votes
0answers
139 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
94 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
1answer
42 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
54 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
0answers
44 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 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
19 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 ...
36
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". ...
39
votes
4answers
12k views

What are common techniques for reducing problems to each other?

In computability and complexity theory (and maybe other fields), reductions are ubiquitous. There are many kinds, but the principle remains the same: show that one problem $L_1$ is at least as hard as ...

15 30 50 per page