Re: The End of the Golden Age of Crypto
On Wed, 27 Nov 2002, Ken Hirsch wrote:
Jim Choate writes:
It's not I who is doing the misreading. I sent this along because I don't
know -your- level, which considering your understanding of
'completeness'...
Peter Fairbrother has said nothing inaccurate about completeness, whereas
your statements about completeness having to do with the ability to write
statements is nonsense.
Not hardly...but apparently Peter isn't the only one who doesn't quite
grasp 'complete'...
A formalism is complete, if for every formula which - in accordance with
it's intended interpretation - is provable within the formalism, embodies
a true proposition, and if, conversely, every true proposition is embodied
in a provable formula.
The Philosophy of Mathematics
An introductory Essay
S. Korner
ISBN 0-486-25048-2 (Dover)
pp 77
And we can of course compare this to Cauchy Completeness...
Definition 6.4
Let X be a metric space, {x_n} a sequence of elements in X. Denote the
distance function by d. The sequence {x_n} is called a Cauchy sequence,
if given e0, there is a positive integer N, so that whenever n and m are
greater than N,
d(x_n, x_m) e
Definition 6.5
A metric space X is complete if every Cauchy sequence {x_n} in X converges
to an element in X (see Theorem 5.1).
Topology - An introduction to the point-set and algebraic areas
D.W. Kahn
ISBN 0-486-68609-4 (Dover)
pp 101
--
We don't see things as they are, [EMAIL PROTECTED]
we see them as we are. www.ssz.com
[EMAIL PROTECTED]
Anais Nin www.open-forge.org
Re: CDR: Re: The End of the Golden Age of Crypto
Jim Choate wrote: Para-consistent logic is the study of logical schemas or systems in which the fundamental paradigms are paradoxes. It's a way of dealing with logical situations in which true/false can't be determined even axiomatically. Most paraconsistent logics deal with paradoxes, but I know of none whose fundamental paradigms are paradoxes. That barely makes sense to me, and is certainly not true. Paraconsistent logics often* allow some but not all sentences within the logic to be both true and false. In paraconsistent logics that have simple notions of true and false** it is usually (at least sometimes) possible to axiomatically determine whether a sentence is true or/and false - they wouldn't be much use if you couldn't! (not that they are much use anyway). * Many logicians would say they all do, according to Vasiliev and Da Costa's original definition. Some would say only some do. And some logician somewhere will disagree with almost anything you say about paraconsistent logics... ** Not all do, eg some have multi-value truths. Some have conditional truths, or truths valid only in some worlds. Some have true, false, both and neither. And so on. As usual, some logicians will disagree with this. For those who might care, paraconsistent logics are usually defined as non-explosive* logics. Ha! There is some argument (lots!**) about that, but it's the generally accepted modern definition (or at least the one most often argued about). * logics in which ECQ does not hold. ECQ = Ex Contradictione Quodlibet, anything follows from a contradiction. In most normal logics, if any single sentence and it's negation can both be proved, then _every_ sentence can be proved both true and false. This property is known as explosiveness. ** For instance, it has recently been shown that some logics traditionally known as paraconsistent, eg Sette's atomic P1 logic, are explosive, contrary to that definition. There are arguments about the meaning of negation as well, all of which confuse the issue. BTW, the name doesn't have anything to do with paradoxes, at least according to the guy who invented it. The para bit is supposedly from an extinct word (I forget the language, Puppy-something, really) for arising out of, coming from. Some say it's from the Greek para- beyond; but I've never heard the paradox story before. I hope this at least interested some, and was not just troll-food. -- Peter Fairbrother
Re: CDR: Re: The End of the Golden Age of Crypto
On Wed, 20 Nov 2002, Peter Fairbrother wrote: Completeness has nothing to do with whether statements can or cannot be expressed within a system. A system is complete if every sentence that is valid within the system can be proved within that system. Introduction to Languages, Machines and Logic A.P. Parks ISBN 1-85233-464-9 pp 240 and 241 -- We don't see things as they are, [EMAIL PROTECTED] we see them as we are. www.ssz.com [EMAIL PROTECTED] Anais Nin www.open-forge.org
Re: The End of the Golden Age of Crypto
Jim Choate wrote: On Wed, 13 Nov 2002, Tyler Durden wrote: Damn what a pack of geeks! (Looks like I might end up liking this list!) When we say complete, are we talking about completeness in the Godelian sense? According to Godel, and formal system (except for the possibility of the oddballs mentioned below--I hadn't heard of this possibility) is incomplete in that there will exist true statements that can not be proven given the axioms of that system. Sorry for the long delay...very busy at work. As far as I am aware formal language definitions of 'complete' and Godel's are the same. I've never seen anything from Godel that indicated otherwise. Your comment is almost correct. Complete means that all true statements can be written (which of course implies that all other statements -must- be false). Incomplete means there are true statements which can't be written in the -limited- syntax of the incomplete system (which again implies there are false statements which can't be made). Completeness has nothing to do with whether statements can or cannot be expressed within a system. A system is complete if every sentence that is valid within the system can be proved within that system. That is the formal definition, as used by Godel in his completeness theorem, in which he proved that FOPL is complete. The converse, that every provable statement is valid, is known as the Soundness theorem. The formal definition of completeness earlier used by Hilbert, Russell et al was almost identical but involved proving false statements to be false as well*. Godel used the same definition in his more famous incompleteness theorem, in which he proved proved that certain systems of logic, later (the next year iirc) proved to be those systems that allow Peano counting, cannot be both complete and consistent. FYI, consistent: no sentence can be proved both valid and false within a consistent system. -- Peter Fairbrother *I assume, I'm not that good at history of mathematics. Godel's completeness theorem also proved that his definition is all that is needed.
Re: The End of the Golden Age of Crypto
On Wed, 13 Nov 2002, Tyler Durden wrote: used for useful computation will suffer from incompletenenss, so I would assume para-consistent logic would fall under that category (is that similar to fuzzy logic?). Not really. Para-consistent logic is the study of logical schemas or systems in which the fundamental paradigms are paradoxes. It's a way of dealing with logical situations in which true/false can't be determined even axiomatically. Very real world... Fuzzy logic (or fuzzy anything else for that matter) is simply statistics applied to some heretofore deterministic/non-heuristic field. I think of it as playing hand grenades or horse shoes ;) You could do fuzzy para-consistent logic if you wanted to (though I can't figure out what I'd want to use it for to be honest). Assume that two or more of your axioms are in conflict some percentage of the time... Sounds more like a problem out of rational agent bargaining and auctions to me ...perhaps there is an app there after all. I have not, however, heretofore considered that there could exist systems that had some form of completeness built in. My intuition (which is easily wrong) tells me that no such system could ever be useful in the real world, but who the heck knows? Until Godel almost everyone thought mathematics was it... Whether it's useful or not isn't the question, the question is can it exist? And the answer is a universal 'No' (or seems to be at this point anyway). -- We don't see things as they are, [EMAIL PROTECTED] we see them as we are. www.ssz.com [EMAIL PROTECTED] Anais Nin www.open-forge.org
Re: The End of the Golden Age of Crypto
On Wed, 13 Nov 2002, Tyler Durden wrote: Damn what a pack of geeks! (Looks like I might end up liking this list!) When we say complete, are we talking about completeness in the Godelian sense? According to Godel, and formal system (except for the possibility of the oddballs mentioned below--I hadn't heard of this possibility) is incomplete in that there will exist true statements that can not be proven given the axioms of that system. Sorry for the long delay...very busy at work. As far as I am aware formal language definitions of 'complete' and Godel's are the same. I've never seen anything from Godel that indicated otherwise. Your comment is almost correct. Complete means that all true statements can be written (which of course implies that all other statements -must- be false). Incomplete means there are true statements which can't be written in the -limited- syntax of the incomplete system (which again implies there are false statements which can't be made). The sticking point isn't the writing of the statements (irrespective of complete or not) but rather the -proof- of their truth. Godel doesn't address the list of statements or how the list was generated but rather the algorithmic process of proof of value. We know axiomatically that we can't write all true statemens in a incomplete system, that's what makes it incomplete. The test is can we tell them apart algorithmically? That question is what puts Godel in the Halting Problem category. The sticking point, and what upset everyone, was that 'complete' and 'provable' aren't the same thing. if you can't write the complete list you of course can't prove all of them. No surpise here. But even if you can write all of the true statements you still can't prove they are true within the system. In other words self-reference destroys the concept of proof as we normally think of it. If you want to prove something you have to step outside of its context (ie meta- views). That destroys the classical/intuitive/naive concept of proof. Godel upsets people because he demonstrates that 'truth' in whatever context one wishes to discuss it is relative. There is no -universal- definition of 'truth'. Reality is observer dependent. Abandon transcendence. -- We don't see things as they are, [EMAIL PROTECTED] we see them as we are. www.ssz.com [EMAIL PROTECTED] Anais Nin www.open-forge.org
Re: The End of the Golden Age of Crypto
On Wed, 13 Nov 2002, Ben Laurie wrote: Jim Choate wrote: What I'd like to know is does Godel's apply to all forms of para-consistent logic as well It applies to any sufficiently complex axiomatic system. Allegedly. Actually it doesn't, it applied to 'complete' systems. There is -no- requirement for the system to be complex. In fact Godel's example about the library of books and the two catalogs (and the question of where to list the catalogs in the catalogs) is quite simple. That is what makes it so striking. Further, completeness doesn't apply to the axioms but rather the list of statements that fall out of the axioms. How you use the axioms. -- We don't see things as they are, [EMAIL PROTECTED] we see them as we are. www.ssz.com [EMAIL PROTECTED] Anais Nin www.open-forge.org
Re: The End of the Golden Age of Crypto
Indeed, I've heard the same. One could argue that for someone to believe in something (religion) so intensely as to shun all moral explanation against this hypothesis and to persist in those beliefs without any proof is akin to schizophrenia. Well, I'm sure this is not an issue that Cypherpunks is going to want to spend a ton of time on, but let's be clear here. There's belief, and then there's faith. With belief,the believer refuses to acknowledge and accpet facts that disagree with their (narrow) worldview. I can't help but put the Creationists in this category. (Even a cursory look at their science makes it clear that there's TONS of information they ignored or explain away with absurd notions.) Faith is a different matter. With faith, the faithful see the facts (as they are commonly understood) and still find a way to believe in something unseen. Belief contradicts reason, faith operates in parallel. I would argue that great scientists operated with a decent amount of the latter, and Galileo is a good example. At the time, the geocentric theory was still able to predict most celestial events better than a heliocentric one. But Galileo had a deeper intuitive sense that something was wrong with that geocentric theory, and its clumsy and mind-boggling complexity. Likewise, every now and then one encounters religious people who recognize the unreasonabilty of what they believe. (Indeed, it's not easy to believe in a God that allows, for instance, the Holocaust to occur). I find these people very different from the believer category, and would place folks like Michelangelo, Kepler, Newton, Maxwell, Kierkegaard, Galileo, St John of the Cross (a Spanish mystic tortured by the inquisition) and many others in this category. As for being akin to Schizophrenia, I'd point out that Schizophrenia is not a mental disorder per se, but a genetically triggered even that causes a measurable, physical degradation in the brain (a Schizophrenic's brain can be identified in autopsies). From: Sam Ritchie [EMAIL PROTECTED] To: Andri Isidoro Fernandes Esteves [EMAIL PROTECTED], Mike Rosing [EMAIL PROTECTED] CC: Cypherpunks [EMAIL PROTECTED] Subject: Re: The End of the Golden Age of Crypto Date: Thu, 14 Nov 2002 19:41:40 -0500 From: Andri Isidoro Fernandes Esteves [EMAIL PROTECTED] Date: Thu, 14 Nov 2002 14:31:41 + To: Mike Rosing [EMAIL PROTECTED] Cc: [EMAIL PROTECTED] Subject: Re: The End of the Golden Age of Crypto On Thursday 14 November 2002 03:50, you wrote: On Wed, 13 Nov 2002, Sam Ritchie wrote: That's the whole deal with the bible, and its various internal contradictions. If anything can be proven true in the bible, then there's no room for faith anymore, which nullifies religious beliefs; and if anything can be proven false, then there's no god, and religion is crushed under the heel of reason. Hurrah, Enlightenment! ~SAM Don't bet on it. I was in a discussion group a week or so ago and one lady who is super devout (of some christian sect, I'm not really sure which one) claimed that she was always testing her faith every day. It really shook me up because I have faith in testing. Religion and reason are not in the same universe! My favorite response on the subject of god is I have no need of that hypothisis. I forget who it's attributed to, but I think it was from the late 1800's. Patience, persistence, truth, Dr. mike The religious person is always battling against reality wich with a minimum of inteligence from the observer always bring doubts on the truth of his faith. It's a state of mind wich can only be compared with mental ilness... (I've read that there are even some neurological similarities between the faithful and the mentaly ill) Indeed, I've heard the same. One could argue that for someone to believe in something (religion) so intensely as to shun all moral explanation against this hypothesis and to persist in those beliefs without any proof is akin to schizophrenia. But that's a whole new kettle of fish. ~SAM The author of that statement: I have no need of that hipotheses was Laplace, french mathematician on answering Napoleon's question in why is book on newtonian mechanics didn't call for god. Andri Esteves _ MSN 8 helps eliminate e-mail viruses. Get 2 months FREE*. http://join.msn.com/?page=features/virus
Re: The End of the Golden Age of Crypto
On Friday 15 November 2002 01:43, Sam Ritchie wrote: Actually, hehe, I've made this comparison before, of religion to a disease. (first off, let me clarify that I have nothing against anyone's religion! I'm looking at this from an outsider's perspective, and harbor no biases.) The torah, for example, has very strict guidelines in it for reproduction of the book, and strongly encourages its followers to go out and make copies. As you mention, religion can act as a virus of sorts, infecting its carrier and urging it to carry the virus to others. The problem with that kind of religious meme is that the original book will refer to a certain time and society.. wich as time passes becomes more and more idyossincratic and out-of-sync... The usual answer to that problem from a religious comunity is to maintain the original lifestyle in wich the memetic code was written has to give its followers a sense of right in reality and truthnes in the written word. You can see for example the orthodox jews. The other ways are: 1) a prophet in direct contact with the god. Example: Any prophetic sect or reformed religion with a charismatic leader 2) a church wich has a outside transcription factor that enables an adaptation to reality. Example: The catholic church, wich has theology as a transcription factor. And the church burocracy to define wich is accepted world-view, justified by theology. (Every 7 years, they revise the list of sins, for example...: These types are not exclusive and usualy evolve from one to other... They all are kind of of an attempt to control the virus, wich is very interesting in itself.. Could we say that organised religion is not itself a disease, but an attempt to control disease?? (to someone's profit of course... : ) My experience in a former religious life, is that the mentally ill are drawn to the religious life... There's even a rare neurological sickness (caused by accidents and brain defects in certain parts of the brain ) in wich the patient has trancesdental experiences and direct contact with god. Ooh, and then there's the apparent tongue of Babel. Glossolalia, or speaking in tongues, is sometimes said to be the human core language. I have read Snow Crash, too. ;) Myself I think that glossofalia is related to the core language, but it's not THE human core language... When 7th day Adventist or any rapture group start speaking in tongues they are usually in a kind of seizure... I think that it's more akin to the universal gramatic of Chomsky let loose and completely haywire. Like if you were working with a voice processor and it's phonem library got all mixed up... (The universal gramatic sets the POTENTIAL languages available to humans, so glossofalic languages sound like languages and even have kind of gramatical order but are not languages.. just attempts to speak with the wrong working-level of the brain) Interestingly, you can reproduce that experience with some mushrooms or roots from the amazon florest, there's even a cult in Brazil that uses them... (more incredible, is that its alucinations are individualistic... someone that believes in buda, will feel Buda... Jeovah, etc... there are people (usually atheists) that say they talked with aliens and space ghosts :))) This drug will even eliminate addictions.. There are heroin, tabaco, etc addicts that will have their addictions eliminated after a section with the so called sacrament... Weird. Very... It's like the drug that was used by a atheist/eastern mistic society in the book The island by Aldous Huxley (his last book). And you can see that tibetan budism, especialy the dalay lama has seen also the potencial children of joining science and eastern misticism. Wich is very, very interesting for the god in our brains seems to clear our deepest fears and pain. Have there ever been studies done on the actual, physical effects of religion on the human brain? It definitely seems valid to say that SOMETHING occurs within the mind when one assumes a faith, something which would definitely be worthwhile to look into... Anyone know? ~SAM Only on meditation of buddist monks, and during prayer. There as not been to knowledge any study on before/after converted persons... And I think there would be no religion that would accept doing that kind of study... (For obvious reasons...) ~~AIFE aka Stackbit
Re: The End of the Golden Age of Crypto
From: Andri Isidoro Fernandes Esteves [EMAIL PROTECTED] Date: Thu, 14 Nov 2002 14:31:41 + To: Mike Rosing [EMAIL PROTECTED] Cc: [EMAIL PROTECTED] Subject: Re: The End of the Golden Age of Crypto On Thursday 14 November 2002 03:50, you wrote: On Wed, 13 Nov 2002, Sam Ritchie wrote: That's the whole deal with the bible, and its various internal contradictions. If anything can be proven true in the bible, then there's no room for faith anymore, which nullifies religious beliefs; and if anything can be proven false, then there's no god, and religion is crushed under the heel of reason. Hurrah, Enlightenment! ~SAM Don't bet on it. I was in a discussion group a week or so ago and one lady who is super devout (of some christian sect, I'm not really sure which one) claimed that she was always testing her faith every day. It really shook me up because I have faith in testing. Religion and reason are not in the same universe! My favorite response on the subject of god is I have no need of that hypothisis. I forget who it's attributed to, but I think it was from the late 1800's. Patience, persistence, truth, Dr. mike The religious person is always battling against reality wich with a minimum of inteligence from the observer always bring doubts on the truth of his faith. It's a state of mind wich can only be compared with mental ilness... (I've read that there are even some neurological similarities between the faithful and the mentaly ill) Indeed, I've heard the same. One could argue that for someone to believe in something (religion) so intensely as to shun all moral explanation against this hypothesis and to persist in those beliefs without any proof is akin to schizophrenia. But that's a whole new kettle of fish. ~~SAM The author of that statement: I have no need of that hipotheses was Laplace, french mathematician on answering Napoleon's question in why is book on newtonian mechanics didn't call for god. Andri Esteves
Re: The End of the Golden Age of Crypto
From: Andri Esteves [EMAIL PROTECTED] Date: Fri, 15 Nov 2002 01:29:26 + To: [EMAIL PROTECTED] Subject: Re: The End of the Golden Age of Crypto On Friday 15 November 2002 00:41, you wrote: Indeed, I've heard the same. One could argue that for someone to believe in something (religion) so intensely as to shun all moral explanation against this hypothesis and to persist in those beliefs without any proof is akin to schizophrenia. But that's a whole new kettle of fish. ~SAM It all depends on the definition of sane... As usually it's a religious force who imposes truth, the faithfull will remain normal ... :) Manipulating the definion of normality is dangerous and only begets the temptation to use it to use other people... We have examples of self-proclaimed atheist societies where this was used for political manipulation: psiquiatric institutions in the former USRR, or even some private institutions in USA that would do that for a hire.. (the case of the frontal lobotomy of Getty's son, ordered by Getty himself (wich probably was age demented by that time, but has people obey to anyone who has a fat checkbook...) We could also invoke memetics and say that religion is like a mental disorder that spreads through a population... A meme infecting minds as they are vulnerable to certain statements, emotions and tautological arguments. Actually, hehe, I've made this comparison before, of religion to a disease. (first off, let me clarify that I have nothing against anyone's religion! I'm looking at this from an outsider's perspective, and harbor no biases.) The torah, for example, has very strict guidelines in it for reproduction of the book, and strongly encourages its followers to go out and make copies. As you mention, religion can act as a virus of sorts, infecting its carrier and urging it to carry the virus to others. My experience in a former religious life, is that the mentally ill are drawn to the religious life... There's even a rare neurological sickness (caused by accidents and brain defects in certain parts of the brain ) in wich the patient has trancesdental experiences and direct contact with god. Ooh, and then there's the apparent tongue of Babel. Glossolalia, or speaking in tongues, is sometimes said to be the human core language. Interestingly, you can reproduce that experience with some mushrooms or roots from the amazon florest, there's even a cult in Brazil that uses them... (more incredible, is that its alucinations are individualistic... someone that believes in buda, will feel Buda... Jeovah, etc... there are people (usually atheists) that say they talked with aliens and space ghosts :))) This drug will even eliminate addictions.. There are heroin, tabaco, etc addicts that will have their addictions eliminated after a section with the so called sacrament... Weird. Wich is very, very interesting for the god in our brains seems to clear our deepest fears and pain. Have there ever been studies done on the actual, physical effects of religion on the human brain? It definitely seems valid to say that SOMETHING occurs within the mind when one assumes a faith, something which would definitely be worthwhile to look into... Anyone know? ~~SAM Yours faithfully, Andri Esteves
Re: The End of the Golden Age of Crypto
Jim Choate wrote: On Wed, 13 Nov 2002, Peter Fairbrother wrote: Jim Choate wrote: What I'd like to know is does Godel's apply to all forms of para-consistent logic as well However you can have eg arithmetics without Peano counting, and so on, and there are (trivial according to Godel, but even he acknowledged that they exist) systems that are both complete (all problems have answers) and consistent (no statement is both true and false). [SSZ: text deleted] Can you do interesting things in such systems? Yes. But you tend to leave intuition behind. What the hell does 'counting' have to do with para-consistent logic on this? Extraordinary claims... Godel's (allegedly?) applies, as Ben pointed out, to any sufficiently complex system. The requirement of sufficient complexity is that the system contains Peano counting. Systems described by Presburger, by Skolem, and by Tarski are among those which do not include Peano counting, and which are both consistent and complete. The relevance of non-Peano counting is simply that you can often do more things in a system that includes some form of counting. One way of stating Godel is No system that includes Peano counting is both consistent and complete. The answer of course is Yes, Godel's applies to Para-Consistent Logic. Trivially, to the extent that all paraconsistent systems are not consistent by definition, you can say yes. You can also say no! Not all paraconsistent systems include Peano counting. Depends what you mean by apply. Godel also has connotations of consequences _within_ the system, eg regarding decideability. Let me introduce a term, Godellike, to describe a system that obeys those supposed consequences. Are paraconsistent systems Godellike? Not necessarily, that's one of the reasons for the development of paraconsistent systems. What really matters is the 'complete', not the 'consistent'. Godel's doesn't apply to incomplete systems because by definition there are statements which can be made which can't be expressed, otherwise it would be complete. You can't prove something if you can't express it since there is no way to get the machine to 'hold' it to work on it. Ahh, those problems of definition again. Complete is normally* taken to mean that every statement expressable within a system is provably true or is provably false within the system. I don't know offhand of any paraconsistent systems that have that property, but it's not impossible afaik. IMO complete has nothing to do with statements which can be made which can't be expressed - though I may be wrong, as I don't understand exactly what that means. -- Peter Fairbrother *As in Godel's other famous theorem, the completeness theorem, which is completely (ouch) different to his incompleteness theorem, the one we are discussing.
Re: The End of the Golden Age of Crypto
Tim May wrote: There are a lot of Godel anecdotes to tell. I never met him. Two things about his theory: 1. There's a more powerful (IMNSHO) formulation of it in terms of algorithmic information theory, usually associated with Greg Chaitin but also drawing on the AIT work of Kolmogorov and others. This says, in informal language, no theory can describe something more complicated than itself. If a theory has 20 bits of complexity, things of 21 bits or more just can't be described/proved. Rudy Rucker has a good description of this in his excellent book Mind Tools. And Chaitin has authored several books and a few very readable Scientific American types of articles. Google will have more on his sites, his papers. I wonder at the real-world relevance. Even Peano arithmetic needs an axiom scheme containing an infinite number of axioms (as does Presburger arithmetic). I also doubt the rigor of Chaitin's work, but I'm just stating an opinion here. He seems to omit except it doesn't apply here, and say more than he has proved. I suppose in terms of 15 axiom 2 rule first order predicate calculus it might be important, but who needs that? (dons flameproof suit, I didn't mean it entirely seriously) 2. This said, my point about not looking to Godelian undecidability sorts of issues for crypto is that it just appears to be too far out there. Nobody, to my knowledge, has ever found a way to make such things useful in crypto...not even things like Presburger arithmetic, which is harder than NP-complete but not yet Godelian undecideable. Here I agree, but I'd add the qualification so far. For instance Paris-Harrington might lead to something interesting (though it's at most tangential to Godelian undecideability). -- Peter Fairbrother
Re: The End of the Golden Age of Crypto
On Thu, 14 Nov 2002, [iso-8859-1] Andri Isidoro Fernandes Esteves wrote: The religious person is always battling against reality wich with a minimum of inteligence from the observer always bring doubts on the truth of his faith. It's a state of mind wich can only be compared with mental ilness... (I've read that there are even some neurological similarities between the faithful and the mentaly ill) I won't disagree, but I think we better live in a bunker! The author of that statement: I have no need of that hipotheses was Laplace, french mathematician on answering Napoleon's question in why is book on newtonian mechanics didn't call for god. thank you! Looks like my date was off by 100 years :-) Patience, persistence, truth, Dr. mike
Re: The End of the Golden Age of Crypto
On Friday 15 November 2002 00:41, you wrote: Indeed, I've heard the same. One could argue that for someone to believe in something (religion) so intensely as to shun all moral explanation against this hypothesis and to persist in those beliefs without any proof is akin to schizophrenia. But that's a whole new kettle of fish. ~SAM It all depends on the definition of sane... As usually it's a religious force who imposes truth, the faithfull will remain normal ... :) Manipulating the definion of normality is dangerous and only begets the temptation to use it to use other people... We have examples of self-proclaimed atheist societies where this was used for political manipulation: psiquiatric institutions in the former USRR, or even some private institutions in USA that would do that for a hire.. (the case of the frontal lobotomy of Getty's son, ordered by Getty himself (wich probably was age demented by that time, but has people obey to anyone who has a fat checkbook...) We could also invoke memetics and say that religion is like a mental disorder that spreads through a population... A meme infecting minds as they are vulnerable to certain statements, emotions and tautological arguments. My experience in a former religious life, is that the mentally ill are drawn to the religious life... There's even a rare neurological sickness (caused by accidents and brain defects in certain parts of the brain ) in wich the patient has trancesdental experiences and direct contact with god. Interestingly, you can reproduce that experience with some mushrooms or roots from the amazon florest, there's even a cult in Brazil that uses them... (more incredible, is that its alucinations are individualistic... someone that believes in buda, will feel Buda... Jeovah, etc... there are people (usually atheists) that say they talked with aliens and space ghosts :))) This drug will even eliminate addictions.. There are heroin, tabaco, etc addicts that will have their addictions eliminated after a section with the so called sacrament... Wich is very, very interesting for the god in our brains seems to clear our deepest fears and pain. Yours faithfully, Andri Esteves
Re: The End of the Golden Age of Crypto
I would however, reverse your two definitions, I think the word belief suggests the more rational, evidence based mental model, faith is a subset belief that requires no evidence. All of us have beliefs (under my schema above) that are evidence based (we believe in the atomic model). Often our beliefs are all tagged with a mental estimate of their surety, based on perception of the evidence and the criticality of the belief, the side effects of it being wrong. Items whose falsehood is not critical can be believed with much less evidence than items whose falsehood is critical. I may believe that Walmart has the best price on a coffeepot, and that is enough to commit a few dollars to the purchase, knowing I could be wrong but that it is not consequential. That same level of belief may not be adequate to purchase a Walmart parachute. It's one thing to believe a newspaper story that a man has the legal name of 'Santa Claus', and a very different to believe he drives flying sleigh reindeer, or that some 100 people wandered in a desert for 40 years WITHOUT A TRACE of evidence, while Egyptian military encampments (only a few dozen men) in that same area and historic timeframe) have been well documented. The key distinction between rationality and religious faith is that scientific, historical and other rational theories (beliefs) are known to be subject to revision, and are constantly evaluated in that framework. Religious faith, however, is not tied to evidence (sometimes searching for evidence is actively discouraged) and is considered true, not really subject to revision. This is, I guess not surprising. A system that in principle takes over one's entire life would have problems if the subjects realized that what is 'right' today might not be right tomorrow. So skepticism is portrayed as evil, critical thinking discouraged and the truthset declared absolute to protect its stability and belief without evidence (faith) is represented as the highest pinnacle of thought. Protecting tat faith becomes more important than reaching quantifiable truths. jay
Re: The End of the Golden Age of Crypto
On Wed, 13 Nov 2002, Tyler Durden wrote: Damn what a pack of geeks! (Looks like I might end up liking this list!) It's full of nut cases too :-) I have not, however, heretofore considered that there could exist systems that had some form of completeness built in. My intuition (which is easily wrong) tells me that no such system could ever be useful in the real world, but who the heck knows? All religions are complete systems. Some people consider them useful, but I'm not sure it classifies as the real world. :-) Patience, persistence, truth, Dr. mike
Re: The End of the Golden Age of Crypto
All religions are complete systems. Some people consider them useful, but I'm not sure it classifies as the real world. :-) I've wondered about that...I suspect that if God exists, then He is true but unprovable in any useful system! -TD PS: According to Godel's biographer, Godel at one point passed around a proof of the existence of God! (But towards the end of his life he also started wearing a surgical mask everywhere and became intensely germaphobic...) From: Mike Rosing [EMAIL PROTECTED] To: [EMAIL PROTECTED] Subject: Re: The End of the Golden Age of Crypto Date: Wed, 13 Nov 2002 08:26:02 -0800 (PST) On Wed, 13 Nov 2002, Tyler Durden wrote: Damn what a pack of geeks! (Looks like I might end up liking this list!) It's full of nut cases too :-) I have not, however, heretofore considered that there could exist systems that had some form of completeness built in. My intuition (which is easily wrong) tells me that no such system could ever be useful in the real world, but who the heck knows? All religions are complete systems. Some people consider them useful, but I'm not sure it classifies as the real world. :-) Patience, persistence, truth, Dr. mike _ STOP MORE SPAM with the new MSN 8 and get 2 months FREE* http://join.msn.com/?page=features/junkmail
Re: The End of the Golden Age of Crypto
Jim Choate wrote:
What I'd like to know is does Godel's apply to all forms of
para-consistent logic as well
And I replied:
No. There are consistent systems, and complete systems, that do not admit
Godel's theorem, but apparently not a system that is both (although even the
last is subject to dispute, and problems of definition).
Sorry, that was a little terse, and just a restatement of Godel. Slightly
drunk.
One way of looking at it is that Godel's theorem only applies in systems
that allow counting according to Peano arithmetic*.
However you can have eg arithmetics without Peano counting, and so on, and
there are (trivial according to Godel, but even he acknowledged that they
exist) systems that are both complete (all problems have answers) and
consistent (no statement is both true and false).
Or, to put it in another and possibly simpler way, if you limit the axioms
in a system in such a way that statements about statements are impossible to
formulate, then Godel doesn't apply.
Can you do interesting things in such systems? Yes. But you tend to leave
intuition behind.
-- Peter Fairbrother
*{axioms: assume Natural numbers, no 0 [can be stated in other ways, that's
original Peano], an add-one function exists, such that if x-add-one =
y-add-one then x=y, and an induction axiom showing there are infinite
numbers: applying Dedekind logic gives ax + ay = a(x+y) and so on, known as
Peano Arithmetic, which is basically ordinary arithmetic in Natural numbers
only, ie no subtraction, division etc}
Re: The End of the Golden Age of Crypto
On Wednesday, November 13, 2002, at 09:12 AM, Tyler Durden wrote: All religions are complete systems. Some people consider them useful, but I'm not sure it classifies as the real world. :-) I've wondered about that...I suspect that if God exists, then He is true but unprovable in any useful system! -TD PS: According to Godel's biographer, Godel at one point passed around a proof of the existence of God! (But towards the end of his life he also started wearing a surgical mask everywhere and became intensely germaphobic...) There are a lot of Godel anecdotes to tell. I never met him. Two things about his theory: 1. There's a more powerful (IMNSHO) formulation of it in terms of algorithmic information theory, usually associated with Greg Chaitin but also drawing on the AIT work of Kolmogorov and others. This says, in informal language, no theory can describe something more complicated than itself. If a theory has 20 bits of complexity, things of 21 bits or more just can't be described/proved. Rudy Rucker has a good description of this in his excellent book Mind Tools. And Chaitin has authored several books and a few very readable Scientific American types of articles. Google will have more on his sites, his papers. 2. This said, my point about not looking to Godelian undecidability sorts of issues for crypto is that it just appears to be too far out there. Nobody, to my knowledge, has ever found a way to make such things useful in crypto...not even things like Presburger arithmetic, which is harder than NP-complete but not yet Godelian undecideable. (One semi-joke is that Godel's results are something every mathematician should learn about but that no working mathematician will ever actually need to use.) --Tim May
Re: The End of the Golden Age of Crypto
Damn what a pack of geeks! (Looks like I might end up liking this list!) When we say complete, are we talking about completeness in the Godelian sense? According to Godel, and formal system (except for the possibility of the oddballs mentioned below--I hadn't heard of this possibility) is incomplete in that there will exist true statements that can not be proven given the axioms of that system. This does not have to be anything complex...a statement like 2+2=4 in some systems may be obviously true, but there's no way to get there given the other axioms in the system. This statement must then be added to the axiom list. After that (old axioms +(the 2+2=4 axiom)), we now have a new formal system, and there will (not might!) exist another statement that is true but unprovable, and so on. In a sense, then, no system is ever complete. As for the nature of the system in which Godelian Incompleteness applies, I'm not enough of a number theorist to remember. BUT...in Turing terms I know that any system that is equivalent to a Turing Machine will have the Incompleteness property. (In addition, Godelian Provability is equivalent, I think, to the Turing Halting Problem. Statements that are true but unprovable will never halt...correct?)In other words, any system that can be used for useful computation will suffer from incompletenenss, so I would assume para-consistent logic would fall under that category (is that similar to fuzzy logic?). I have not, however, heretofore considered that there could exist systems that had some form of completeness built in. My intuition (which is easily wrong) tells me that no such system could ever be useful in the real world, but who the heck knows? From: Jim Choate [EMAIL PROTECTED] To: [EMAIL PROTECTED] Subject: Re: The End of the Golden Age of Crypto Date: Wed, 13 Nov 2002 07:27:44 -0600 (CST) On Wed, 13 Nov 2002, Peter Fairbrother wrote: Jim Choate wrote: What I'd like to know is does Godel's apply to all forms of para-consistent logic as well And I replied: No. There are consistent systems, and complete systems, that do not admit Godel's theorem, but apparently not a system that is both (although even the last is subject to dispute, and problems of definition). Which is the point of Godel's, you're arguing in circles here son. Perhaps you've been out in the sun too long ;) [SSZ: text deleted] However you can have eg arithmetics without Peano counting, and so on, and there are (trivial according to Godel, but even he acknowledged that they exist) systems that are both complete (all problems have answers) and consistent (no statement is both true and false). [SSZ: text deleted] Can you do interesting things in such systems? Yes. But you tend to leave intuition behind. What the hell does 'counting' have to do with para-consistent logic on this? Extraordinary claims... Para-consistent logic is logic where statements -can't by definition- be given an absolute true/false, in fact para-consistent logic allows axiomatic statements that are in direct conflict. The 'para' comes from 'paradox'. Considering the state of the real world I doubt you'd leave very much 'intuition behind' by moving to a para-consistent model. The answer of course is Yes, Godel's applies to Para-Consistent Logic. Irrespective of whatever logic you wish to use, it will be sensitive to Godel's because Godel's is a sort of halting theorem that says that with respect to decidability you can't devise an algorithm in any language or representation that will -guarentee- and answer to the question of whether a particular question has an answer. Godel's applies irrespective of the contents of any given system, paradoxical or consistent be damned. What really matters is the 'complete', not the 'consistent'. Godel's doesn't apply to incomplete systems because by definition there are statements which can be made which can't be expressed, otherwise it would be complete. You can't prove something if you can't express it since there is no way to get the machine to 'hold' it to work on it. -- We don't see things as they are, [EMAIL PROTECTED] we see them as we are. www.ssz.com [EMAIL PROTECTED] Anais Nin www.open-forge.org _ The new MSN 8: smart spam protection and 2 months FREE* http://join.msn.com/?page=features/junkmail
Re: The End of the Golden Age of Crypto
Jim Choate wrote: What I'd like to know is does Godel's apply to all forms of para-consistent logic as well It applies to any sufficiently complex axiomatic system. Allegedly. Cheers, Ben. -- http://www.apache-ssl.org/ben.html http://www.thebunker.net/ There is no limit to what a man can do or how far he can go if he doesn't mind who gets the credit. - Robert Woodruff
Re: The End of the Golden Age of Crypto
On Wed, 13 Nov 2002, Peter Fairbrother wrote: Jim Choate wrote: What I'd like to know is does Godel's apply to all forms of para-consistent logic as well And I replied: No. There are consistent systems, and complete systems, that do not admit Godel's theorem, but apparently not a system that is both (although even the last is subject to dispute, and problems of definition). Which is the point of Godel's, you're arguing in circles here son. Perhaps you've been out in the sun too long ;) [SSZ: text deleted] However you can have eg arithmetics without Peano counting, and so on, and there are (trivial according to Godel, but even he acknowledged that they exist) systems that are both complete (all problems have answers) and consistent (no statement is both true and false). [SSZ: text deleted] Can you do interesting things in such systems? Yes. But you tend to leave intuition behind. What the hell does 'counting' have to do with para-consistent logic on this? Extraordinary claims... Para-consistent logic is logic where statements -can't by definition- be given an absolute true/false, in fact para-consistent logic allows axiomatic statements that are in direct conflict. The 'para' comes from 'paradox'. Considering the state of the real world I doubt you'd leave very much 'intuition behind' by moving to a para-consistent model. The answer of course is Yes, Godel's applies to Para-Consistent Logic. Irrespective of whatever logic you wish to use, it will be sensitive to Godel's because Godel's is a sort of halting theorem that says that with respect to decidability you can't devise an algorithm in any language or representation that will -guarentee- and answer to the question of whether a particular question has an answer. Godel's applies irrespective of the contents of any given system, paradoxical or consistent be damned. What really matters is the 'complete', not the 'consistent'. Godel's doesn't apply to incomplete systems because by definition there are statements which can be made which can't be expressed, otherwise it would be complete. You can't prove something if you can't express it since there is no way to get the machine to 'hold' it to work on it. -- We don't see things as they are, [EMAIL PROTECTED] we see them as we are. www.ssz.com [EMAIL PROTECTED] Anais Nin www.open-forge.org
Re: The End of the Golden Age of Crypto
From: Tyler Durden [EMAIL PROTECTED] Date: Wed, 13 Nov 2002 12:12:34 -0500 To: [EMAIL PROTECTED], [EMAIL PROTECTED] Subject: Re: The End of the Golden Age of Crypto All religions are complete systems. Some people consider them useful, but I'm not sure it classifies as the real world. :-) I've wondered about that...I suspect that if God exists, then He is true but unprovable in any useful system! -TD That's the whole deal with the bible, and its various internal contradictions. If anything can be proven true in the bible, then there's no room for faith anymore, which nullifies religious beliefs; and if anything can be proven false, then there's no god, and religion is crushed under the heel of reason. Hurrah, Enlightenment! ~~SAM PS: According to Godel's biographer, Godel at one point passed around a proof of the existence of God! (But towards the end of his life he also started wearing a surgical mask everywhere and became intensely germaphobic...) From: Mike Rosing [EMAIL PROTECTED] To: [EMAIL PROTECTED] Subject: Re: The End of the Golden Age of Crypto Date: Wed, 13 Nov 2002 08:26:02 -0800 (PST) On Wed, 13 Nov 2002, Tyler Durden wrote: Damn what a pack of geeks! (Looks like I might end up liking this list!) It's full of nut cases too :-) I have not, however, heretofore considered that there could exist systems that had some form of completeness built in. My intuition (which is easily wrong) tells me that no such system could ever be useful in the real world, but who the heck knows? All religions are complete systems. Some people consider them useful, but I'm not sure it classifies as the real world. :-) Patience, persistence, truth, Dr. mike _ STOP MORE SPAM with the new MSN 8 and get 2 months FREE* http://join.msn.com/?page=features/junkmail
Re: The End of the Golden Age of Crypto
On Wed, 13 Nov 2002, Sam Ritchie wrote: That's the whole deal with the bible, and its various internal contradictions. If anything can be proven true in the bible, then there's no room for faith anymore, which nullifies religious beliefs; and if anything can be proven false, then there's no god, and religion is crushed under the heel of reason. Hurrah, Enlightenment! ~SAM Don't bet on it. I was in a discussion group a week or so ago and one lady who is super devout (of some christian sect, I'm not really sure which one) claimed that she was always testing her faith every day. It really shook me up because I have faith in testing. Religion and reason are not in the same universe! My favorite response on the subject of god is I have no need of that hypothisis. I forget who it's attributed to, but I think it was from the late 1800's. Patience, persistence, truth, Dr. mike
Re: The End of the Golden Age of Crypto
Tim wrote: It would be nice to have crypto systems based on at least problems which have been shown to be NP-complete. Even here, one has to be careful. The knapsack cryptosystem, based on the NP-Complete problem Subset Sum, crashed and burned spectacularly a number of years back. The world is replete with NP-Complete problems whose random instances have a near-zero probability of being difficult to solve. I think what you want here, at least for key exchange, is something along the lines of a well-designed message digest function, which has the magic property that f(g(x)) = g(f(x)) so you can do Diffie-Hellman. This would be a lot more difficult to break than either factorization or discrete log, neither of which is likely NP-Hard, and when all the chips have settled, perhaps as weak as N^2. -- Eric Michael Cordian 0+ O:.T:.O:. Mathematical Munitions Division Do What Thou Wilt Shall Be The Whole Of The Law
Re: The End of the Golden Age of Crypto
Tyler Durden wrote: (I believe that the non-existence of the last prime number is also unprovable.) Could you give some details/ a ref please? The usual proof by contradiction is easy and well-known. Suppose there is a last prime. Generate a list of all the primes sooner than or equal to the supposed last prime (in practice this could take some time, but not infinite time). Multiply them all together and add 1. Result has remainder of 1 for all primes in list. Therefore either the result (which must ' be later than supposed last prime) is prime, or the result is a multiple of primes not on the list (which must ' be later than supposed last prime). Therefore there must be a later prime than the supposed last prime. Should be valid in some non-Godelian systems as well. Doesn't apply in all fields though, but ordering in those fields where it doesn't apply is usually* impossible, so you can't even define a last prime there. Of course we can't even prove cogito ergo sum, but I don't think that was your point. -- Peter Fairbrother Non-mathematicians should replace sooner with smaller, later with larger, and last with largest. ' There are some ordering considerations I have left out, but they all work out in the field of Natural numbers. *Always?
Re: The End of the Golden Age of Crypto
Look, I have no idea what your background is, beyond the fact that you're new to the list and are obviously neither Edward Norton nor Brad Pitt. I suggest you take a look at some of the books on algorithms, especially the Harel book. Garey and Johnson is the classic on NP-completeness, but it's way too dry and technical to start out on. As for my background it's Optics/Physics/EE, and for the last 8 years worked with Erbium Doped Fiber Amplifiers, DWDM and SONET (ie, optical telecom). (Interestingly, my work in Telecom did once cause me to enter the only joint classified/unclassified NSA facility, as well as DARPA and DISA.) In case it matters, I've got a sack of papers and patents in that area, and was fairly well-known in those circles. After experiencing a couple of layoffs over the last year, I retreated to the relative sanctity and security of Wall Street, where I now work (and no, I'm not Pitt/Norton but my nome d'plume gives you a hint of the kind of company I work for, and it ain't insurance!) The references are well-appreciated, but wrt the complexities of the algorithmic issues, I am more interested in knowing what the basic issues are (as well as what may not be known). At this stage, and for various reasons, I find that the potential social implications are what I am most interested in, but the newbie in me is trying to sort out what low-level details must be known in this context, while hopefully making an interesting point or two along the way. As for Godelian intractability, I didn't see that as necessarily an issue of complexity. Godel showed that given any formal system, there are statements that will certainly exist that are true but unprovable from within that system (mathematical truth is often confused with provability). Factorization may simply be one of those things that is difficult, but unprovably so, in which case it will forever and always be such. This may mean that we will end up living with factorization for a long time and yet never know if it's actually difficult or not. Again, sorry to all for being a little chatty and clumsy at this point. From: Tim May [EMAIL PROTECTED] To: [EMAIL PROTECTED] Subject: Re: The End of the Golden Age of Crypto Date: Tue, 12 Nov 2002 11:04:32 -0800 On Tuesday, November 12, 2002, at 10:22 AM, Tyler Durden wrote: Well, my main point was that the fact that we are not certain about the difficulty in factorization is not necessarily due to our current lack of knowledge about the issue (and to be rectified one day as we look back and laugh at our previous naivety). In this case I was trying to reference Godel and the notions of unprovability...it is possible that factorization is inherently difficult and that the difficulty is a fact that is innately unprovable. (Yeah, I goofed on the larget prime issue...when I try to pull something out of pure memory my hit rate isn't very high) In a sense, this IS a restatement of his original point, but with an emphasis on the fact that our faith in the difficulty of factorization may be more than wishful thinking. This is an issue that a huge number of very smart mathematicians have tackled and see no real traction on. So our collective intuition on this issue may have reality on our side. (In which case we will never look back and laugh.) As for finding a process that has already proven to be innately difficult, I do find that an interesting notion. Certainly many such processes exist and have been identified...was factorization chosen because the encryption process used very little hardware (back when that mattered)? No, this was a non-issue. Fact is, nobody has found a way to get what I'll call the trapdoor/asymmetry property with known NP-complete problems such as the Hamiltonian cycle problem (and a slew of NP-complete problems which are of course in a sense the same problem). Why this may be the case is unknown (to me, at least). There are many books on complexity, NP-completeness, and algorithms. I like David Harel's Algorithmics a lot (he later re-issued it in a different form, but I favor the earlier version). Oded Goldreich has a new book on crypto...my copy is floating around somewhere here in my house, so I can't check it right now. The point is that R, S, and A found factoring worked for the trapdoor/asymmetric (easy in one direction, very hard in the other) properties needed. Factoring has not been proved to be NP-complete. There are problems even harder than NP-complete, of course. Fame awaits anyone who finds a way to use the Hamiltonian cycle, polynomial satisfiability, etc., or one of the domino tiling (harder than NP-complete) classes of problems for crypto in general. (There are famous examples of using Hamiltonian cycles for giving zero knowledge proofs. I wrote one up here for the list about 10 years ago...it may be findable by searching on the right keywords. But using one of the NP-complete problems to
Re: The End of the Golden Age of Crypto
On Tuesday, November 12, 2002, at 11:04 AM, Tim May wrote: (There are famous examples of using Hamiltonian cycles for giving zero knowledge proofs. I wrote one up here for the list about 10 years ago...it may be findable by searching on the right keywords. But using one of the NP-complete problems to produce a ZK certificate is not the same as something like RSA encryption...though one would think there _must_ be a way to make it solike I said, fame awaits someone who figures this out.) I dug up the last article I did on this. Here it is: * To: [EMAIL PROTECTED] * Subject: CDR: An Introduction to Complexity, Hamiltonian Cycles, and ZeroKnowledge Proofs--Part 1 * From: Tim May [EMAIL PROTECTED] * Date: Sat, 4 Nov 2000 13:05:07 -0800 * Cc: Olav [EMAIL PROTECTED] * In-Reply-To: [EMAIL PROTECTED] * Old-Subject: An Introduction to Complexity, Hamiltonian Cycles, and ZeroKnowledge Proofs--Part 1 * References: [EMAIL PROTECTED] * Reply-To: [EMAIL PROTECTED] * Sender: [EMAIL PROTECTED] At 2:20 PM -0500 11/4/00, dmolnar wrote: On Sat, 4 Nov 2000, Jim Choate wrote: On Sat, 4 Nov 2000, Declan McCullagh wrote: NP problems, on the other hand, are those that can be solved in nondeterministic polynomial time (think only by guessing). NP includes P. Actualy any time that can't be described using a polynomial (i.e. a0 + a1x + a2x^2 + ...) is NP. For example something that executes in factorial or exponential time is NP. I'm sorry - by the definitions I know, Declan has it closer. I'm not sure what you're getting at with any time that can't be described... or something that executes in factorial or exponential time. As far as I know, NP is a class of *problems*, not a class of running times or even a class of algorithms. And I'm going to give a completely informal, but I hope useful, introduction. Though formalism is very important, and jargon is useful, I suspect that all the talk of succinct certificates, oracles, reducibility, nondeterministic polynomial time, Co-NP, etc., isn't very useful to someone just coming to this stuff for the first time. I figure understanding math comes from thinking about specific problems, drawing pictures, mulling things over, drawing more pictures, and basically just becoming one with the problem. Formal definitions then begin to make a lot more sense. While Bourbaki may favor only the tersest of explanations, I think they are dead wrong. (Fair warning: I knew a lot more about this stuff in 1992 when I was reading Garey and Johnson, Harel, etc. and trying to figure out the zero knowledge papers of Goldwasser and her colleagues. These days, terms like Co-NP are not in my daily repertoire of concepts I have a good handle on. But the basic ideas don't need such formal definitions. It's more important to have some _intuition_ about common problems and then see the obvious connections with crypto. David Molnar and others are much better versed in the current lingo.) So, the German guy, Olav, who asked about what P and NP and all that stuff means should think of a specific problem. The Travelling Salesman Problem is one problem that's a lot of fun to think about, for complexity issues (and also for specific algorithms, like simulated annealing, heuristic search, genetic programming, etc.). However, I'm going to pick the Hamiltonian Path (or Hamiltonian Circuit) problem for most of my discussion. It's equally fun, and is one of the canonical NP-complete examples. It turns out that these problems are all similar in a deep way to each other. Though there may not be obvious links between Hamiltonian paths, tiling problems in the plane, Go problems on generalized Go boards, grammar problems, Monkey puzzles, the Minesweeper game mentioned in this thread, and so on, it turns out that they share deep similarities. In fact, with some effort (polynomial time effort, so to speak) one problem can be converted to another. Hence the notion that if one could find an easy algorithm to solve one, one would have solved all of them. (And always keep in mind that these problems are considered in their _general_ forms, with something like N cities, M x N tile arrays, a Go board of N x N grid points, and so on. Any _specific_ instance is not the essence, though of course a specific instance may still be hideously complicated to solve. And slight factors of 2 or 20 or even 20 million, or, indeed, anything short of exponential in N, are not important. This is often called Big O notation, e.g, the complexity/effort goes as O (N^3) or O (N!). For exact definitions of these kinds of terms, consult any of the many books on this stuff; I'm just trying to provide the motivation and basic ideas here.) TRAVELLING SALESMAN PROBLEM Take 10 cities in Europe. For example: Berlin, Paris, Madrid, Rome, Marseilles, Hannover, Geneva, Amsterdam, Warsaw, and London. The TSP (Travelling Salesman
Re: The End of the Golden Age of Crypto
Mike Duvos writes: Break a code, go to jail. Even a silly code, like XOR. This is probably true. In the current political climate, anyone who posts turbo-factor on the Internet, and destroys secure communications worldwide, can probably expect the secret tribunal followed by lethal injection, after being smeared in the press as a traitor. Remember, if you're not on Shrub's bandwagon, helping him beat his little drum, you're with the terrorists. The 00's will be the Golden Age of something else. Superintelligent AI perhaps. Opposite ends of the complexity spectrum. Superintelligent AI can break strong crypto. Strong crypto means superintelligent AI requires intractable computation. Perhaps the complexity landscape permits only a middle ground. Not particularly smart AI, and not particularly strong crypto. Even Rivest, Shamir, and Adleman knew essentially no number theory. ... cryptography is based on faith, much like tea-leaf reading. A .sigfile quality observation, I'm sure. We have absolutely no hard mathematical evidence that factoring is any harder than multiplying or taking square roots, ... I've always found it irksome that we haven't managed to move beyond combination of congruences/homomorphism-based factoring techniques. There has to be a simpler technique for unraveling multiplication, which, after all, is a very simple and straightforward manipulation of bits. It is likely our ability to generate algorithms by a direct grep of all formulas having a specific form, and perhaps in the near future, all formulas under a certain length, will uncover many simple but difficult to directly derive formulas that do useful things. Automated mining of reality for awesome but simple equations whose derivations are just a bit too messy for humans to manually perform will probably play an increasingly important role in the future of mathematics. Ramanujan, as I recall, produced a lot of stuff which proved to be correct, but which seemed impossible to arrive at without knowing it in the first place. Delete PGP, Win a Free Turkey, Har. Yes, folks. It's the End of the Golden Age of Crypto. Well, I'm not quite ready to run out and close the patent office yet. We still have quantum cryptography and one-time pads, which, if our current understanding is correct, are intrinsically unbreakable. If one-way functions turn out to have been a crack-induced hallucination, quantum cryptography can replace public key systems for secure key exchange. Some crypto-notable, I forget who, proposed putting satellites in orbit which transmitted high bandwidth random noise, which one would XOR with ones data before sending it. The recipient, also receiving the satellite signal, would know the starting bit in the random garbage, and could decrypt. Since it would be impractical to record the output of the satellite over any period of time, this would preclude messages being later decrypted, no matter how much CPU was thrown at them, as the information to decrypt them would no longer exist. Techniques like this, with satellite-based quantum crypto key exchange services, would permit us to retain a reliable national crypto infrastructure, should complexity-based systems fall apart under increased combinatorial scrutiny. -- Eric Michael Cordian 0+ O:.T:.O:. Mathematical Munitions Division Do What Thou Wilt Shall Be The Whole Of The Law
