Timeline for Existence of unknowable algorithms ?
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 6, 2013 at 20:44 | comment | added | user6976 | The point of my previous request is: if you are looking for an undecidable mass problem (a set of inputs and a set of admissible inputs, the problem is when an input is admissible), then you need to look for an algorithm (in your case - an algorithm to find an algorithm). If your problem is not a mass problem, you are looking for a non-provable statement which is a completely different ball game (independence from ZFC and such things). Please clarify. | |
| Apr 6, 2013 at 20:17 | comment | added | user6976 | @Loïc: It may help if you formulate your question in a most standard way, as a "mass problem". What exactly is the problem which you want undecidable, i.e. what is the input set and when an input should be recognized? | |
| Apr 6, 2013 at 20:12 | comment | added | user6976 | I see. The new formulation is much less vague. I (or somebody else) need to think more about it. | |
| Apr 6, 2013 at 14:19 | comment | added | Loïc Teyssier | Thanks for your answer! Yet I don't feel it relates fully to my admitedly vague quetion, although its nature pleases me better than other answers do. Maybe my edit clarifies what I meant. | |
| Apr 5, 2013 at 18:43 | history | edited | user6976 | CC BY-SA 3.0 |
fixed an error; added 154 characters in body
|
| Apr 5, 2013 at 18:39 | comment | added | user6976 | Yes, I was not careful enough. I will change the answer. | |
| Apr 5, 2013 at 18:17 | comment | added | Benjamin Steinberg | @Mark, I believe Slobodoskii's theorem doesn't say exactly what you want. It says you cannot decide give a finite presentation <X|R> whether a word in X is 1 in every X-generated finite group satisfying the relations R. Note <X|R> can present an infinite group. If you know a finite presentation presents a finite group, you can solve the yes part by enumerating all consequences of R and the no part enumerating finite groups. | |
| Apr 5, 2013 at 14:52 | history | answered | user6976 | CC BY-SA 3.0 |