Take any list:
1234
2345
1357
4567
and create a certain new entry to the list by making a new number composed of the first digit of item 1, the second digit of item 2, the third didgit of item 3 and so on. This gives us :
1357
Now change all the digits to anything other than what they are, say +1
2468
This must be a new number, not in the list, because it differs, by definition since we just changed them all, from item 1 in digit 1, differs from item 2 in digit 2, and so on.
Suppose we add that number to the list, how then do we get a new number?
1234
2345
1357
4567
2468
We can't use diagonalisation as above because each number only has 4 pieces of information in it to change and we need 5 - that is, there is no diagonal. I imagine this solution works +"0" to the start
01234
02345
01357
04567
02468
Then our diagonal is 02368 and changing all the digits say +4 Mod(10) gives us 46702 which is not in the list.
We could use the other diagonal of course. In fact there are n! (n factorial) diagonals to chose from. In the case of 4 that is 24 diagonals.
And taking any one of these numbers there are b^n where b is the number of digits to chose from (i.e. the base - 1). In the decimal cases above that is 9^4 = 6561 possible numbers.
Not sure how to prove the next bit, but fairly obviously going through all the diagonals and changing to all the possible digits (with a lot of duplication) this method could find any of the missing 9996 numbers in the list of 4 (taking 0000 as a number also).
In reality numbers of countably infinite so this method can just add a 0 each time and go on forever always discovering a new number of greater length for the list.
Even at infinity the method works because 0 + infinity is a new digit (unlike infinity + 0!). This is the conundrum of the fully booked infinite hotel which can never-the-less always take a new guest! Not however by handing out the key to the infinite + 1 room, but rather by getting everyone to move to the next door room (quite within the rules of infinity) and thus freeing room #1 for the new guest.
So anything that can be listed automatically has exception by definition of Cantor's extraordinarily simple and powerful argument!
Hofstadter in GEB makes the splendid point that Godel, Tarski and the host of other proofs are versions of this argument, proceeding by making a list and then finding the new term that is not in the list. For example in Godel once the list of all provable statements is made, proof is already doomed ;-)
So turning to my own obsession the +1 hypothesis. This was the real start of the SRH quest, and it revolves around the sense that a "system" must be incomplete, in that an observer can "know" more about the system than it can itself. The outside view always being larger and more substantial than the inside view. What Hoftsadter calls the Meta level. Tho i'd call it exo versus endo levels. The problem is how to characterise something so general as a system.
Any system will have a "state". That is to say a particular collection of data that determines the stage of processing. A static system like this sentence has just a simple value. But a looping program in a computer will step from state to state as it works through the calculation. If it were possible to group all the states of a system together in a long string (like Godel's proofs in Principia Mathematica) then we could represent any finite system at all as a countable number. Turing's never terminating Turing machines (NTTMs) just become real numbers, and the halting problem isn't a problem anymore.
The damage then is already done because we can always find exceptions to this list of all systems, altho oddly the exceptions to the NTTMs are very huge of size Aleph 2! Quite what non terminating systems which have infinite solution spaces are like I have no idea i.e. computers that work in continuous data ... except don't we know one... The brain? We assume it works by discrete (finite) neuron triggering, but we also know that neurons work by summing action potentials and this data is not discrete but continuous in nature. Maybe a brain can't be simulated digitally and only in analogue... does analogue computing exist? check it up. What is analogue logic? Analogic ;-) ... apparently the astrolabe counts as an analog computer taking us back to Herpatia and Alexandria. How odd if there were hidden depths to this ancient computing after all?
Anyway I have digressed and this doesn't shed any light on the +1 hypoithesis... try again another day... off to fix the patio... tho 1st update on thoughts on train last night (from written notes)...
The Komogorov complexity of a system would be the shortest algorithm that simulates the system.
Now an algorithm takes some data and some combination rules and recursively applies them until the answer is achieved... how does a system know it has got the answer? Obviously the test to end the alogithm is independent of the "nature" of the answer (that incidentially is a very good example of SRH!) cos we can't know it's the answer until we have the answer!
So in Principia Mathematica, for example, all the provable statements have k-complexity set by the relevant axioms and the shortest list of derivation rules.
But what then of the Godel statement for a particular set up of PM? It can't be derived from the axioms by the derivation rules. So there is no algorithm to compute it (within PM) so it has an undecidable k-complexity.
Doesn't the Godel statement prove that self-reference is actually impossible?
Just thinking... if PM has the ability to Godel encode and also to reverse Godel encode then can't it just reverse Godel encode the Godel number of the Godel statement? Which proves what I suspected in my naivete that actually PM can't do Godel encoding itself and Godel encoding is a meta event... in other words the so called "self"-reference relies upon a perspective that is already meta the system! By suprise doesn't this prove the original form of the SRH that true self-reference is impossible because if it were possible then any system could decode the godel number of the Godel statement and thus create a contradiction.
===
If we look at a derivation of a sentence in logic as analogous to the "explanation" of that sentence (i.e. taking what we know and showing how something we don't know can be derived from it) - which suggests that learning a new thing must come before it is explained!! (as I have learned from trying to tutor kids - they need to discover it first and then once they know it, it can be explained - you can't teach new things by explanation). So Godel stataments can't ever be explained but once found always become the basis of new explanations. They also mean that a system cannot be defined in totality.
Now above I used the idea of the string of discrete states to define a system.
Would the PM system be the string of all possible combinations of derivation rules on axioms? But the PM system doesn't then have the Godel statement as a state because that statement is not derivable!!! So do we then define the system as the string of all possible wff (well formed formulas) defined by the grammatical system. But then we know this can't be defined recursively (using PM).
So a problem defining the complexity of a system because it has two forms!
Now Turing Machines versus Logical systems - what is the difference.
It seems to me that there is a Turing machine to produce every number. This means that there is a Turing machine to compute anything (finite). The only thing they can't computer are the infinite sequences (mentioned above) which are the Turing Halting problems. But why not include infinite sequences (defined recursively) as above?
Anyway in a Universal Turing machine which can compute any number the analogous Godel statements must be machines that output infinite numbers.
Why can't PM produce any number however? And if it can therefore the Godel number of every statement? So actually PMs limitation is the same as a Turing machine... I don't understand :-(
Need think some more... why didn't I do a degree in IT or maths then I'd have the background for all this then! And if anyone who knows ever reads this (which is 1 reason I put it on the web wishing for some serendipity) give us a gentle nudge in the right direction save me the searching in the dark ;-)
No comments:
Post a Comment