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 e>0, 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: > > 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 A "non-mathematical" "easy to read" primer (quotes from Springer-Verlag). I don't have a copy. If Alan Parkes says Godelian completeness is other than the definition above then he is wrong - possible, he is a multimedia studies teacher, and afaik is not a mathematician - but I suspect you misread him. FYI, I just googled "completeness godel". First five results plus some quotes are at the bottom. Five minutes, which I could have spent better. RTFM. -- Peter Fairbrother ... Googling "completeness" and "Godel", first five results: http://www.math.uiuc.edu/~mileti/complete.html No simple definition of completeness. Nice intro to models though. www.chaos.org.uk/~eddy/math/Godel.html "Completeness is the desirable property of a logical system which says that it can prove, one way or the other, any statement that it knows how to address." www.uno.edu/~asoble/pages/1100gdl.htm "Completeness = If an argument is valid, then it is provable" http://www-cs-students.stanford.edu/~pdoyle/quail/questions/11_15_96.html "A complete theory is one contains, for every sentence in the language, either that sentence or its negation." http://www.wikipedia.org/wiki/Kurt_Godel -- link to http://www.wikipedia.org/wiki/Goedels_completeness_theorem "It states, in its most familiar form, that in first-order predicate calculus every universally valid formula can be proved."
Re: The End of the Golden Age of Crypto
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.
Re: The End of the Golden Age of Crypto
On Wed, 27 Nov 2002, Peter Fairbrother wrote: > A "non-mathematical" "easy to read" primer (quotes from Springer-Verlag). I > don't have a copy. If Alan Parkes says Godelian completeness is other than > the definition above then he is wrong - possible, he is a multimedia studies > teacher, and afaik is not a mathematician - but I suspect you misread him. 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'... > FYI, I just googled "completeness godel". First five results plus some > quotes are at the bottom. Five minutes, which I could have spent better. I've already send several mathematical references that refer to completeness and what it means. You apparently didn't read them. That speaks for itself. You'd rather bitch than learn. Hint: you can't prove truth (which is what Godel is about) without first listing the statements in the 'complete' language. Think about what you said and eventually it will dawn on you -what- you said. Ta ta. -- 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, 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
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, 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
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 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
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
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
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
> 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
> 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
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
> 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) The belief (faith) center is somewhere in the frontal cortex and that mutation was essential for development of the civilisation as we know it, which basically boils down to brainwashing believers into beating the shit out of nonbelievers (and these, being independent individuals, never managed to properly organise to resist), which is evolutionary sustainable (when the shit gets beaten out of you it takes your mind of sex.) So, technically speaking, it's more specialisation than mental illness. = end (of original message) Y-a*h*o-o (yes, they scan for this) spam follows: Yahoo! Web Hosting - Let the expert host your site http://webhosting.yahoo.com
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 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) 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
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
> 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, 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
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
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
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
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
"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
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
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
Re: The End of the Golden Age of Crypto
> On Tue, 12 Nov 2002, Tyler Durden wrote: > > > 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"). Actually you have to include 'false' as well. The uncertainty is symmetric. The point of differentiating 'truth' and 'provability' is to recognize you can't prove them wrong either. 'Provability' is the ability to answer definitively as compared to what the actual answer is. That is the fundamental distinction. It's a sort of halting problem once you see this (as compared to the actual state at the halt). Godel's simply states in a different way that some things never stop, and you can't always tell which ones they are. What I'd like to know is does Godel's apply to all forms of para-consistent logic as well -- 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
"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
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
On Tue, 12 Nov 2002, Tyler Durden wrote: > 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!) Yeah, EETimes reports telcom still leads in layoffs. Glad to hear you can still eat! > 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. Maybe the history of epistimology would be useful? > 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. Factoring is sub-exponential in complexity. Elliptic curve discrete log is (still) fully exponential. I'm not sure about lattice theory (see NTRU). There's a lot of mathematical relationships to be discovered yet. What was "difficult" 50 years ago is now high school level knowledge. If that kind of thing doesn't continue, humans will just stagnate and die. A sub probelm to all this is "what is thinking?" Why do we even bother? > Again, sorry to all for being a little chatty and clumsy at this point. I don't know of any other way to approach it, so keep chatting! 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
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 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.) 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. I would also steer clear of issues of Godelian undecidability at this point. The types of "intractability" at issue here are a lot less "complex" in the hierarchy. --Tim May
Re: The End of the Golden Age of Crypto
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)? From: Tim May <[EMAIL PROTECTED]> To: [EMAIL PROTECTED] Subject: Re: The End of the Golden Age of Crypto Date: Tue, 12 Nov 2002 09:48:27 -0800 On Tuesday, November 12, 2002, at 07:13 AM, Tyler Durden wrote: This may be true, but the conclusion that might easily be reached isn't. According to the number theorists (particularly post-Godel), factorization may easily be one of those things that... 1) Is inherently dificult 2) and the fact that it is inherently difficult is unprovable. Yeah, a restatement of his point. It would be nice to have crypto systems based on at least problems which have been shown to be NP-complete. This may mean that not only is there no "hard evidence", there may never be. This being the case (and it most probably is), then we may always have to live with this uncertaintyand ain't that life? (I believe that the non-existence of the "last" prime number is also unprovable.) I don't follow you here. The Greeks knew the proof that there is no largest prime, a proof which can be written down in a paragraph. (If one believes in excluded middle proofs as opposed to constructivist proofs, which in this context is a reasonable belief.) --Tim May _ Add photos to your messages with MSN 8. Get 2 months FREE*. http://join.msn.com/?page=features/featuredemail
Re: The End of the Golden Age of Crypto
On Tuesday, November 12, 2002, at 07:13 AM, Tyler Durden wrote: This may be true, but the conclusion that might easily be reached isn't. According to the number theorists (particularly post-Godel), factorization may easily be one of those things that... 1) Is inherently dificult 2) and the fact that it is inherently difficult is unprovable. Yeah, a restatement of his point. It would be nice to have crypto systems based on at least problems which have been shown to be NP-complete. This may mean that not only is there no "hard evidence", there may never be. This being the case (and it most probably is), then we may always have to live with this uncertaintyand ain't that life? (I believe that the non-existence of the "last" prime number is also unprovable.) I don't follow you here. The Greeks knew the proof that there is no largest prime, a proof which can be written down in a paragraph. (If one believes in excluded middle proofs as opposed to constructivist proofs, which in this context is a reasonable belief.) --Tim May
Re: The End of the Golden Age of Crypto
Actually, that was quite a post from Mr Duvos. And while I am in position to respond to most of what he has written, I would like to take slight issue with the following: "Such cryptography is based on faith, much like tea-leaf reading. We have absolutely no hard mathematical evidence that factoring is any harder than multiplying or taking square roots, or of the existence of easily computed functions with computationally intractable inverses" This may be true, but the conclusion that might easily be reached isn't. According to the number theorists (particularly post-Godel), factorization may easily be one of those things that... 1) Is inherently dificult 2) and the fact that it is inherently difficult is unprovable. This may mean that not only is there no "hard evidence", there may never be. This being the case (and it most probably is), then we may always have to live with this uncertaintyand ain't that life? (I believe that the non-existence of the "last" prime number is also unprovable.) As for arguments concerning "short cuts" that occur from Ramanujan-like flashes of human insite, you have now wandered into some very difficult waters...I suspect that some of the AI folks would argue that your pi example is the result of much deeper algorithmic processes that occur in the brain, and that we can't observe yet. SOme (such as Penrose) would disagree, and argue that human creativity leverages very deep connections between the brain and the quantum world...this would always be beyond even very powerful silicon (though non-Quantum) machines. From: Mike Duvos <[EMAIL PROTECTED]> To: [EMAIL PROTECTED] Subject: The End of the Golden Age of Crypto Date: Sun, 10 Nov 2002 16:45:21 -0800 (PST) Tim May wrote: > So, in these four areas real code is being generated. These get > mentioned on the list...one just has to notice them, and remember. > My main point is to refute the defeatism that often is clothed in the > language of cynicism and ennui. Much is still being done. It isn't > getting the attention of the press, which is probably a good > thing. (They have moved on to other topics. And nobody is being > threatened with jail, so crypto is no longer as edgy as it was when PRZ > was facing prosecution, when crypto exports were illegal, when Clipper > was in the news.) Crypto export has been decriminalized, and cryptanalysis programs are now illegal "circumvention devices" under the DMCA. I am hard pressed to view this as an improvement. If DECSS and Advanced eBook Processor produce an exhaltation of prosecutors bent on putting the authors in jail, I doubt we'll be hearing if someone invents DE-SSH or DE-AES. This greatly reduces my faith in the robustness of ciphers, particularly those that have been around to have their tires kicked for a decade or two. Break a code, go to jail. Even a silly code, like XOR. The 90's were the Golden Age of public access to crypto, largely driven by public key cryptography and the need for people to do secure communication over the Internet without physically meeting to exchange keys. The 00's will be the Golden Age of something else. Superintelligent AI perhaps. > Even Rivest, Shamir, and Adleman knew essentially no number > theory. One of them got the idea that maybe the difficulty of factoring > could be used as the core for what they were doing...I have also heard > that the idea came from another on the staff at MIT, but I won't get > into that right now. Then they "crammed" and learned what they needed > to learn about stuff like Euler's totient function, methods for finding > primes, etc. It was enough. Such cryptography is based on faith, much like tea-leaf reading. We have absolutely no hard mathematical evidence that factoring is any harder than multiplying or taking square roots, or of the existence of easily computed functions with computationally intractable inverses. We infer the existence of such things solely from the observation that the human mind has not yet produced solutions to such problems. If they were really easy, we conjecture, someone would have figured out the answer by now. Well, maybe. Evidence is begining to emerge which suggests that such a view may be fundamentally flawed, and just as most humans cannot multiply 100 digit numbers in their heads, so there are countless wonderful and simple formulas whose derivation from scratch is so complex that no one will ever find them simply by trying to derive them directly. Are hard problems hard because they have no simple solutions, or simply because their simple solutions lie slightly beyond the range of our current deductive radar? Are they hard, or are we simply bad programmers? Compelling evidence for the latter explanation is beginning to mass. Consider, for instance, the following simple power series (Bailey,Borwein,Plouffe) for Pi as a sum of inverse powers of 16. Multiply by a power of 16 and take the fractional part, and you c
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"