Tuesday, 16 October 2018

Looking for simple expression of SRH

I'm sure Taski has been here but recently looking at what I think are the two major proofs by contradiction isn't it built on something much simpler? Turing proves that a computation that sets out to determine whether computations in general halt cannot determine whether it itself halts. Or more precisely he generates a "spanner" in the works which does the opposite of what this function expects. Likewise Godel does the same thing using a function that declares the provability of statements, and a spanner that states that a certain statement is not provable, namely itself. All quite sophisticated logic. But consider this most simple version of the liar paradox:

If we suppose it is possible to list all possible functions (here we go the start of an Diagonalisation proof) and so give them a number that can be used to refer to them, then if f(x) is a function then #f(x) means the function at row f in the list.

A function Is0(x) is defined like this:

int Is0(x) {
if (#x(x) == 0) return 1;
if (#x(x) != 0) return 0;
}

What is the result of Is0(#Is0)? In other words does Is0(#Is0) == 0?

If it does equal 0 then it would return 1 and if it doesn't then it would return 0. We have a contradiction... however Turing steps in because it is infinitely recursive and would loop forever as indeed does the "I am a liar" statement. It never resolves to a fixed truth value and keeps looping forever. Is0(x) is thus provably a partial function and Is0(#Is0) is undefined: it doesn't halt. As SRH suggests the domain of total functions and numerical output is not enough once you get self reference and the meta domain of non-halting functions is opened up according to the +1 or Hamlet principle.

So then Turing makes a meta statement not about the numerical output but about the function operation itself... whether it halts or not. Godel does the same making a statement whether there is a string of statements that generates the statement.

Like Cantor infinitely exploding the types of infinity, doesn't diagonalisation suggest that the domain of computable functions also expands so that there are levels of Non-Halting function.. I believe that would mean an infinite ascent of Oracle machines.

No comments:

"The Jewish Fallacy" OR "The Inauthenticity of the West"

I initially thought to start up a discussion to formalise what I was going to name the "Jewish Fallacy" and I'm sure there is ...