Re:Godel, Omega, Algorithmic Complexity Theory???
on
Downloading The Mind
·
· Score: 1
Your analogy is incorrect.
Godel's theorem shows that if a set of axioms and an algorithm for proving theorems from these axioms are chosen (ie. a formal axiomatic system is constructed), this system is either capable of proving a result which is false, or incapable of proving a result which is true. The proof of godel's theorem does not proceed within the axiomatic system chosen, but constructs a statement and then appeals to the reader to _observe_ that the axiomatic system is either incomplete or incorrect. There is no way of proving Godel's theorem correct from within the axiomatic system under consideration as it will either consider the Godel statement unassailably true (incorrectly) or have nothing at all to say about it.
It has been shown that simply choosing a second formal system with which to analyse the first does not eliminate the problem as the second system will have its own Godel statement, with the same attendant difficulties.
The point is that an informed reader can "see" the validity of Godel's theorem, but it is impossible to prove it in its most general form within a given axiomatic system.
Since any algorithm is equivalent to an axiomatic system (I think Church proved this one), the mathematician is capable of doing something which an algorithm absolutely cannot.
I agree that Roger Penrose shot himself in the foot by pissing everyone off with his arrogance and going off on his quantum gravity tangent, but this argument does carry weight and is a hell of a lot more sophisticated and difficult to contradict than your simplified version. It may well be that the saddest thing about Penrose' fall from grace is that this argument has been unfairly dismissed by a large number of people who simply do not understand it.
As far as Chaitin and Omega are concerned, the results show Godel incompleteness to be not simply a matter of a single obscure statement within each formal system, but a far more general problem of how much complexity a formal system can exhibit. Regardless of whether you agree with the argument above, you should read this. (He has nothing to say about AI, etc. Though I have a feeling that might be because for a mathematician that might mean instant loss of credibility).
Incidentally, in claiming to be the same as the Godel-based argument, your simplified version assumes that Roger Penrose' mind is equivalent to a computer. Therefore to use your simplified argument to argue for that very proposition is circular.
This is correct. Higher power is used, but I believe one estimate is that to get comparable coverage to a GSM network requires up to four times as many base stations. The situation is further complicated by the fact that as a result of the code-based multiple access technology the effective size of a cell varies with the number of users connected, making the design of networks with good coverage non-trivial. I used to work for Ericsson as a RF Engineer for UMTS networks (though these opinions are, of course, my own) and, although I would quite like to be proven wrong, I get the strong impression that 3G will never deliver. The "2Mb/s" bandwidth is a theoretical maximum for a terminal right next to an otherwise unused base station. 365 Kb/s (asymmetric, with 64 on the uplink) is a much more realistic figure. Providing even this with good coverage requires an enormous number of base stations. Even with groovy multimedia apps, there is a limit to how much people will be willing to pay for this technology. IMHO (IANAA - I am not an accountant), this is going to be a hell of a lot less than the many billions which have already been spent on licenses and networks. Cue Chopins "Funeral March".
The only 3G system I know about is the European UMTS system, whose air interface operates on WCDMA (the same technology as the American system, which I believe is imaginatively called WCDMA). This system is particularly well known for being resistant to interference. The original CDMA (Code Division Multiple Access - the W stands for Wideband) system was originally developed by the American military to provide resistance to jamming. The key characteristic of WCDMA is that each handset signal is spread across a wide chunk of the spectrum (around 1.9 GHz in UMTS), by applying a code which is chosen to render the signal orthogonal to those of the other handsets. Applying the code at the other end to retrieve the original narrow-band signal has the beneficial side-effect of spreading any narrow-band interference across the original broad area of the spectrum, thus reducing its intensity. To effectively jam the system would involve swamping the entire UMTS spectrum, which would take a massive amount of power. As for red lights causing interference in the ~2GHz spectrum - well, that's just plain silly. Amusing troll, though.
Godel, Omega, Algorithmic Complexity Theory???
on
Downloading The Mind
·
· Score: 2, Insightful
Roger Penrose may generally be considered to have gone off at a bit of a tangent to reality since "The Emperor's New Mind", but whatever your position on whether quantum (gravity) effects can be important in the workings of a mind, his argument that Godel's theorem shows that a mathematician is capable of using his mind to accomplish a feat which a turing machine is mathematically incapable of replicating has not yet been satisfactorily answered. G.M.Chaitin's discovery of Omega and work on algorithmic complexity theory appears to lend even more weight to the idea that the mind is not simply an information processing device. Many (most) objects which perform a task do not do so solely by processing information and often can only be approximately simulated by computers. Just because the computer is the only device we have so far constructed which is capable of complex, flexible behaviour does not imply that all objects which are capable of such behaviour are computers. On a side note, claiming that we will have strong AI by 2029 is like predicting that Bin Laden will be caught at 12:49 PM on the 12th of June 2003. My horoscope carries more weight.
Yeah, I'll rise to the troll, but only because I'm in a major bad mood today and there are so few comments on this article that the first thing I saw was this idiot.
It isn't astronomy, it's communications, you ignorant fuckwit.
There they are in court claiming it's beyond their means simply to come up with a modular version of Windows, and now here we see them about to rewrite the whole bloody thing. In fact they'll probably get the court case(s) to drag on long enough for them to complete the project before any remedies are put in place, so that once it's released and everybody discovers that the built-in mind-sequestering technology is inseparable from the basic OS features it'll be too late and they'll be able to use the same argument.
3K being really rather a low temperature, the cosmic backround radiation is (way down) in the infrared, so I guess we can safely deduce that an empty patch of the night sky would be roughly, er, black.
Posted this earlier as an AC, but I'd quite like to know the answer so here it is again with that extra mod point.
If the algorithmic complexity is the length of the shortest program which can produce a given string, would its value not depend on the universal Turing machine the program is expected to run on? Eg, say A and B are two strings, T1 and T2 are turing machines. Let N1()and N2() be the turing numbers of the shortest programs you could use to specify a string using T1 and T2 respectively.
Surely you could artificially define T1 and T2 so that
K1(A) = 1
K1(B) = 2
K2(A) = 2
K2(B) = 1
Here the algorithmic complexity of A is smaller than that of B if T1 is used and vice-versa if T2 is used (assuming the program is just the turing number written in binary, ie 1 or 10).
If I am not talking utter crap here, wouldn't that mean that the algorithmic complexity of an program does not only depend on the algorithm itself, but on an arbitrary choice of Turing machine against which to measure the complexity, making it pretty useless as a measure of how long it would take to develop the software.
Incidentally, when I refer to the Turing machine here, I am not talking about the Turing machine the software we are developing will run on, but the one on which the program which generates its string runs on - ie. the one used to define its algorithmic complexity. They may be the same thing, but I don't see how making them the same would make the algorithmic complexity a more valid indication of software development time.
Slashdot Mirror
Order yours!
Your analogy is incorrect.
Godel's theorem shows that if a set of axioms and an algorithm for proving theorems from these axioms are chosen (ie. a formal axiomatic system is constructed), this system is either capable of proving a result which is false, or incapable of proving a result which is true. The proof of godel's theorem does not proceed within the axiomatic system chosen, but constructs a statement and then appeals to the reader to _observe_ that the axiomatic system is either incomplete or incorrect. There is no way of proving Godel's theorem correct from within the axiomatic system under consideration as it will either consider the Godel statement unassailably true (incorrectly) or have nothing at all to say about it.
It has been shown that simply choosing a second formal system with which to analyse the first does not eliminate the problem as the second system will have its own Godel statement, with the same attendant difficulties.
The point is that an informed reader can "see" the validity of Godel's theorem, but it is impossible to prove it in its most general form within a given axiomatic system.
Since any algorithm is equivalent to an axiomatic system (I think Church proved this one), the mathematician is capable of doing something which an algorithm absolutely cannot.
I agree that Roger Penrose shot himself in the foot by pissing everyone off with his arrogance and going off on his quantum gravity tangent, but this argument does carry weight and is a hell of a lot more sophisticated and difficult to contradict than your simplified version. It may well be that the saddest thing about Penrose' fall from grace is that this argument has been unfairly dismissed by a large number of people who simply do not understand it.
As far as Chaitin and Omega are concerned, the results show Godel incompleteness to be not simply a matter of a single obscure statement within each formal system, but a far more general problem of how much complexity a formal system can exhibit. Regardless of whether you agree with the argument above, you should read this. (He has nothing to say about AI, etc. Though I have a feeling that might be because for a mathematician that might mean instant loss of credibility).
Incidentally, in claiming to be the same as the Godel-based argument, your simplified version assumes that Roger Penrose' mind is equivalent to a computer. Therefore to use your simplified argument to argue for that very proposition is circular.
This is correct. Higher power is used, but I believe one estimate is that to get comparable coverage to a GSM network requires up to four times as many base stations.
The situation is further complicated by the fact that as a result of the code-based multiple access technology the effective size of a cell varies with the number of users connected, making the design of networks with good coverage non-trivial.
I used to work for Ericsson as a RF Engineer for UMTS networks (though these opinions are, of course, my own) and, although I would quite like to be proven wrong, I get the strong impression that 3G will never deliver. The "2Mb/s" bandwidth is a theoretical maximum for a terminal right next to an otherwise unused base station. 365 Kb/s (asymmetric, with 64 on the uplink) is a much more realistic figure. Providing even this with good coverage requires an enormous number of base stations.
Even with groovy multimedia apps, there is a limit to how much people will be willing to pay for this technology. IMHO (IANAA - I am not an accountant), this is going to be a hell of a lot less than the many billions which have already been spent on licenses and networks.
Cue Chopins "Funeral March".
The only 3G system I know about is the European UMTS system, whose air interface operates on WCDMA (the same technology as the American system, which I believe is imaginatively called WCDMA).
This system is particularly well known for being resistant to interference. The original CDMA (Code Division Multiple Access - the W stands for Wideband) system was originally developed by the American military to provide resistance to jamming.
The key characteristic of WCDMA is that each handset signal is spread across a wide chunk of the spectrum (around 1.9 GHz in UMTS), by applying a code which is chosen to render the signal orthogonal to those of the other handsets. Applying the code at the other end to retrieve the original narrow-band signal has the beneficial side-effect of spreading any narrow-band interference across the original broad area of the spectrum, thus reducing its intensity. To effectively jam the system would involve swamping the entire UMTS spectrum, which would take a massive amount of power.
As for red lights causing interference in the ~2GHz spectrum - well, that's just plain silly.
Amusing troll, though.
Roger Penrose may generally be considered to have gone off at a bit of a tangent to reality since "The Emperor's New Mind", but whatever your position on whether quantum (gravity) effects can be important in the workings of a mind, his argument that Godel's theorem shows that a mathematician is capable of using his mind to accomplish a feat which a turing machine is mathematically incapable of replicating has not yet been satisfactorily answered. G.M.Chaitin's discovery of Omega and work on algorithmic complexity theory appears to lend even more weight to the idea that the mind is not simply an information processing device.
Many (most) objects which perform a task do not do so solely by processing information and often can only be approximately simulated by computers. Just because the computer is the only device we have so far constructed which is capable of complex, flexible behaviour does not imply that all objects which are capable of such behaviour are computers.
On a side note, claiming that we will have strong AI by 2029 is like predicting that Bin Laden will be caught at 12:49 PM on the 12th of June 2003. My horoscope carries more weight.
Yeah, I'll rise to the troll, but only because I'm in a major bad mood today and there are so few comments on this article that the first thing I saw was this idiot.
It isn't astronomy, it's communications, you ignorant fuckwit.There they are in court claiming it's beyond their means simply to come up with a modular version of Windows, and now here we see them about to rewrite the whole bloody thing.
In fact they'll probably get the court case(s) to drag on long enough for them to complete the project before any remedies are put in place, so that once it's released and everybody discovers that the built-in mind-sequestering technology is inseparable from the basic OS features it'll be too late and they'll be able to use the same argument.
3K being really rather a low temperature, the cosmic backround radiation is (way down) in the infrared, so I guess we can safely deduce that an empty patch of the night sky would be roughly, er, black.
Posted this earlier as an AC, but I'd quite like to know the answer so here it is again with that extra mod point.
If the algorithmic complexity is the length of the shortest program which can produce a given string, would its value not depend on the universal Turing machine the program is expected to run on? Eg, say A and B are two strings, T1 and T2 are turing machines. Let N1()and N2() be the turing numbers of the shortest programs you could use to specify a string using T1 and T2 respectively.
Surely you could artificially define T1 and T2 so that
K1(A) = 1
K1(B) = 2
K2(A) = 2
K2(B) = 1
Here the algorithmic complexity of A is smaller than that of B if T1 is used and vice-versa if T2 is used (assuming the program is just the turing number written in binary, ie 1 or 10).
If I am not talking utter crap here, wouldn't that mean that the algorithmic complexity of an program does not only depend on the algorithm itself, but on an arbitrary choice of Turing machine against which to measure the complexity, making it pretty useless as a measure of how long it would take to develop the software.
Incidentally, when I refer to the Turing machine here, I am not talking about the Turing machine the software we are developing will run on, but the one on which the program which generates its string runs on - ie. the one used to define its algorithmic complexity. They may be the same thing, but I don't see how making them the same would make the algorithmic complexity a more valid indication of software development time.