diff options
author | Kaz Kylheku <kaz@kylheku.com> | 2015-01-15 20:07:48 -0800 |
---|---|---|
committer | Kaz Kylheku <kaz@kylheku.com> | 2015-01-15 20:07:48 -0800 |
commit | 53af38e6a5a251c7674511ff7985f2d1ab78c481 (patch) | |
tree | 4fa7a1f7388941f53a3e8f3c482458d18f2cb384 | |
parent | ecfd7f2a67f4e15d13391b8c3c6d346c3d3504cb (diff) | |
download | halt3-53af38e6a5a251c7674511ff7985f2d1ab78c481.tar.gz halt3-53af38e6a5a251c7674511ff7985f2d1ab78c481.tar.bz2 halt3-53af38e6a5a251c7674511ff7985f2d1ab78c481.zip |
Wording improvements.halt3-1.6
-rw-r--r-- | proof-sketch.txt | 26 |
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. |