Timeline for How to show the function is not Turing computable?
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 23, 2017 at 22:56 | vote | accept | TechCrap | ||
| Jan 23, 2017 at 22:56 | vote | accept | TechCrap | ||
| Jan 23, 2017 at 22:56 | |||||
| Jan 23, 2017 at 21:06 | vote | accept | TechCrap | ||
| Jan 23, 2017 at 22:56 | |||||
| Jan 23, 2017 at 20:57 | answer | added | Yuval Filmus | timeline score: 3 | |
| Jan 23, 2017 at 20:57 | answer | added | Dino Rossegger | timeline score: 3 | |
| Jan 22, 2017 at 16:03 | comment | added | TechCrap | Could you please provide a sample solution? So I could see the right way to go for exercises like this one. | |
| Jan 22, 2017 at 16:00 | comment | added | TechCrap | So it's enough to show that we can map it onto the halting problem? I.e. having a set of instances of (A, D), where A is $\Phi_y(n)$ and D is some x from $N$, we get pairs in S such as ($\Phi_y$, 1), ($\Phi_y$, 2), ...., now H halts if $\Phi_y(n) $ = n. Thus we can map it onto the halting problem, therefore it's not computable? | |
| Jan 22, 2017 at 15:41 | comment | added | Yuval Filmus | I don't quite understand your proof. Try a reduction from the halting problem. | |
| Jan 22, 2017 at 14:55 | comment | added | Raphael | Our reference question may be of help. | |
| Jan 22, 2017 at 14:55 | comment | added | Raphael | Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! | |
| Jan 22, 2017 at 12:47 | history | asked | TechCrap | CC BY-SA 3.0 |