Suppose you write this recursive program:
bool DetermineSomeThing(int input) {
if DetermineSomeThing(input) return false;
return true;
}
It's a contradiction like "I am false." But importantly it also doesn't halt. The reason it doesn't halt is that it is defined in terms of itself for all calls.
In this case:
bool DetermineSomeThing(int input) {
if input == 0 return true;
if DetermineSomeThing(input-1) return false;
return true;
}
This will eventually return a value (I'm guessing true if input was even and false if it was odd) because the recursion scans through the intergers and it doesn't recurse for the value 0.
But if all values are deterkined in terms of itself you have an infinite loop and it doesn't halt.
The SRH has a problem with things determined in terms of themselves. Now apparently such hermeneutic circles are not catastrophic. The standard definition of integers begins with the integer '0'. So given an integer you can construct the rest. So actually it doesn't define what an "integer" is only the sequence. And in meaning in general there are no fixed starting points or foundations, you work backwards and deduce starting points from your already embedded position within the system. Being inside a loop or system is not catastrophic, so that to make any move you must use the system you already have.
But under circumstances like above it is catastrophic and you never get out of the system. It never halts.
Now Turing has already proved that there is no fixed way of determining whether a functions halts. If there was you could it to create a contradiction. If Halting maps to SRH then perhaps there is no way to determine if SRH applies or not! You can never tell in advance whether a particular application of self reference will create contradiction. In other words "self reference" remains an undefined bogey man that can always throw up surprises in an undetermined way!
OK quick appraisal:
Wait a second. I was trying to show that SRH is more fundamental than the Halting problem since it is with Self-Reference that the Halting proof is constructed. The contradiction supposes that an algorithm exists and then uses it to create a contradictory input to the algorithm. Since the input function knows whether it should halt or not it can be perverse and just reverse this behaviour. This is like the recursive function above that uses its own value to be perverse altho the looping in Turing proof is not causes by the recursion, it loops after making the decision.
Quick add: not all loops are recursive:
10 GOTO 10
keeps jumping to the same jump instruction. It it not looping because of logic where the result is determined in terms of itself e.g. "I am false" where re-evaluation occurs for ever. Which incidentally suggests that "I am true" should not halt either? Why should we interpret the false statement as an infinite loop and not the true version? Loosely you could say that jumping to an instruction is part of determining the result and if it jumps to the jump instruction then its saying to get the result go here, which says the same ad infinitum. It can be written as recursion:
int GetResult() {
return GetResult()
}
But are all loops the equivalent of recursion and so self reference? Hmmm how to determine the answer to that?
No comments:
Post a Comment