summaryrefslogtreecommitdiffstats
path: root/proof-sketch.txt
diff options
context:
space:
mode:
Diffstat (limited to 'proof-sketch.txt')
-rw-r--r--proof-sketch.txt26
1 files changed, 14 insertions, 12 deletions
diff --git a/proof-sketch.txt b/proof-sketch.txt
index 4a79e07..73c2bf5 100644
--- a/proof-sketch.txt
+++ b/proof-sketch.txt
@@ -84,23 +84,25 @@ Background:
Motivation:
- Some researchers disbelieve the proof of the halting problem, claiming
- that it is a contrived trick and that the test cases which are generated
- by that trick are somehow invalid, the implication being that deciders
- may be legitimately excused for not being able to to determine whether or not
- these cases halt.
+ Some researchers take issue with the proof of the halting problem, claiming
+ that even though it is true, it is a contrived trick and that the test cases
+ which are generated by that trick are somehow invalid, the implication being
+ that deciders may be legitimately excused for not being able to to determine
+ whether or not these cases halt, and that these cases do not represent
+ a true, palpable limit on computability.
It has been proposed that a three-valued version of the halting problem
- can provide the necessary framework. Under this notion, the halting function
- is augmented to have a third possible return value, so that for each
- <program, input> pair, it assigns the value true, false or error. The new
- error value has some meaning such as that <program, input> test case
- constitutes a test case which is trying to break the decider through some
- self-referential trick.
+ can provide the necessary framework which allows halting deciders to
+ effectively diagnose situations when they are subject to "unfair"
+ test cases. Under this notion, the halting function is augmented to have a
+ third possible return value, so that for each <program, input> pair, it
+ assigns the value true, false or error. The new error value has some meaning
+ such as that <program, input> test case constitutes a test case which is
+ trying to break the decider through some self-referential trick.
This paper presents a proof sketch which suggests that the three-valued
halting function is also not total computable. Using a more refined trick,
- three-valued halting deciders can be shown to be incorrect. For any
+ three-valued halting deciders can be shown to fail. That is to say, for any
halting decider, a test case can be found such that it incorrectly returns
error in a situation when no trick is going on: a situation when that decider
could be altered to return true or false without being contradicted.