Timeline for What is the amount of programs for which we can solve the halting problem?
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 19, 2018 at 22:38 | comment | added | Mike Battaglia | The "success rate" is an interesting concept. Have there been any results published regarding the success rate for various partial halting oracles, or what the maximum possible success rate could be? | |
| Sep 17, 2016 at 17:44 | comment | added | Andrej Bauer | Attempt 1 and Attempt 2 are relevant because the way you phrased your question it reads as a question about Attempt 1 or Attempt 2. Your formulation does not speak about Attempt 3. Your teminology is messed up. And I think it's not just terminology, you actually do not see the difference between Attempt 2 and Attempt 3. That's what everyone here is trying to teach you. So, again, please read carefully what I and all the other people are saying. | |
| Sep 17, 2016 at 17:42 | comment | added | Andrej Bauer | What you say about P1 and P2 is ok, but what if you have to consider infinitely many problems P1, P2, P3, ...? Then, how will you compose D1, D2, D3, ... into a single procedure? | |
| Sep 17, 2016 at 16:13 | comment | added | user56834 | My question is about attempt 3. I still don't quite understand what attempt 1 has to do with this, but regarding attempt 2: if we have a decision procedure D1 for program P1 and a (possibly different) D2 for P2, then we can create D which, if it is fed P1, applies D1, and if it is fed D2, applies P2. This is why I assumed that whether every program is halting-decidable by a different decision procedure or by the same (assuming they are halting-decidable) is irrelevant, since a new universal decision procedure can be constructed. In any case, It is the value Sp that you defined that I'd like. | |
| Sep 16, 2016 at 14:47 | history | edited | Andrej Bauer | CC BY-SA 3.0 |
deleted 1 character in body
|
| Sep 16, 2016 at 13:17 | comment | added | Andrej Bauer | I elaborate the answer. Please read carefully and try to understand why what you are saying is a moving target. | |
| Sep 16, 2016 at 13:13 | history | edited | Andrej Bauer | CC BY-SA 3.0 |
added 891 characters in body
|
| Sep 16, 2016 at 13:01 | comment | added | user56834 | My textbook defines that a set is decidable iff there is a decision procedure for it. So I don't really understand why you're introducing the complication of there being a decision procedure but it not being computable. If a decision procedure is not "computable", then I would say the procedure simply doesn't exist. Perhaps the terminology in my textbook is different from what is employed elsewhere. In any case, are there rough estimates of Sp? even if it is not well defined, which would seem to me personally to be very unlikely, there could be some estimate of a value around which Sp hovers? | |
| Sep 16, 2016 at 12:48 | history | answered | Andrej Bauer | CC BY-SA 3.0 |