Class #5: Knowledge Representation, Analytic vs. Synthetic, and Zero-Knowledge Proofs

Which is the more fundamental concept: “knowing how” or “knowing that”?  Is it possible to “know” that 37×43=1591, yet not “know” the prime factors of 1591?  If so, what is the thing that you know in the one case but not in the other?

Do you know an infinite number of propositions?

Do statements about computational processes blur the distinction between analytic and synthetic knowledge?  Is the statement that a quantum computer (say) will output a particular answer “more analytic” or “more synthetic”?  Does the answer change if we instead consider the distinction between a priori and a posteriori knowledge?

Does every mathematical proof depend for its validity on implicit physical assumptions (for example, that a demon isn’t changing what’s written on the page as you read it), as Deutsch argues?  Is the situation different for the modern “proof protocols” studied in theoretical computer science and cryptography (zero-knowledge proofs, quantum proofs, etc.), than for traditional proofs?  Or do these proof protocols merely make more vivid a dependence on physics that was already present in traditional proofs?

Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.

28 Responses to Class #5: Knowledge Representation, Analytic vs. Synthetic, and Zero-Knowledge Proofs

  1. Avril says:

    In class when we were discussing the difference between implicit and explicit knowledge, it reminded me of a talk that I saw about how even after people have learned definitions and scientific facts, their judgments are still influenced by the intuitive theories they used to have as kids: http://csjarchive.cogsci.rpi.edu/proceedings/2011/papers/0043/paper0043.pdf

  2. “Does every mathematical proof depend for its validity on implicit physical assumptions (for example, that a demon isn’t changing what’s written on the page as you read it), as Deutsch argues?”

    I think this line of reasoning leads us to a surprising face-off between Deutsch and Penrose: Deutsch’s claim is indisputable unless Penrose is right that humans can comprehend logical truths in a special “hollistic” way that’s irreducible to simply going through the time-steps of a verification procedure one by one and terminating on accept.

    • Mike says:

      “Deutsch’s claim is indisputable unless Penrose is right that humans can comprehend logical truths in a special “hollistic” way that’s irreducible to simply going through the time-steps of a verification procedure one by one and terminating on accept.

      Well, the face-off isn’t that surprising, is it?. Is our “mind” governed by the laws of physics “substantially” as we understand such laws today? Perhaps there is something about humans or the laws of physics that sets us apart . . . . but otherwise I’m afraid that we’re left we trying to figure out how to “program” human “creativity”. Knowing it’s possible, but not having a very good intuition about how to accomplish it.

  3. Deutsch’s demon in the brain is unproductive skepticism. We can demonstrate this by drawing out the full consequences of such a demon.

    Consider a true proposition P, which our demon would like to trick us into not believing. How does the demon do this? Let’s suppose the demon influences our perception, tricking us into believing P is the same as some different, true proposition P’. If we were to sit down, and attempt to enumerate all the propositions, or perform any of the other mechanisms which are “more formal”, we may notice a strange thing happening when we reach proposition P. We might even get suspicious of the demon P. So, the demon would have to squash any second-order thoughts which call the results of our first-order perception into question. And likewise for third-order thoughts, and so on.

    But that’s not all. Suppose we build a machine for solving mathematical proofs, based on the laws of silicon and physics. If we assume we’ve built this machine correctly, the machine should discover the status of P. So we cannot have built the machine properly: now the demon needs to interfere with our understanding of physics and semiconductors, and some how make it the case that any machine we build will be defective in the same way we were.

    In sum, assuming that humans have a capacity for scientific inquiry, the demon needs to present a near consistent worldview with P elided from it, such that human curiosity and inquiry is unable to stumble upon the handiwork of the demon. This is a tall order for any such demon: it requires reality changing on par with a brain in a vat. Perhaps it truly is unproductively skeptical.

    This is not to say we don’t have our little demons, giving us little cognitive biases and systematic errors. But the triumph of science and formal systems is that, with our higher-order faculties, we can overcome these troubles.

    • A devli’s advocate could argue the following, maybe: The demon could save all this work by simply tampering with the cognitive mechanism we use to map physical systems to formal structures. It is (arguably) likely that we rely on the same basic mechanism in all the cases in which we map concreta into abstracta, whether the concreta be semiconductors or inkmarks on paper.

      The best response to the devil’s advocate, I think, would be to say that even if our cognitive mechanism is the same no matter what concreta we are dealing with, we use different cognitive mechanisms for different *abstracta*. So even if we could have a cognitive corruption that would sabotage both our set-theoretical reasoning in paper proofs and our reasoning that a given machine is a set-theory proof system, it’s unlikely that this very same cognitive corruption will affect our PA reasoning (or our reasoning that a given machine is a PA proof system) in the very same way.

    • Philosophically speaking, like the question of whether I am a brain in a vat, the demon is unproductive skepticism because it is by definition undetectable and undefeatable. It makes no sense to worry about the possibility whenever we discuss the topic of human thought. (It may, however, be more interesting from a computational perspective.)

      On the other hand, looking at the demon scenario on its own raises interesting questions. For example, suppose the demon doesn’t directly alter our perception of a written proof, but instead keeps our thoughts and imaginations from pursuing certain paths. Every nontrivial proof is the result of someone having an insight as to which logical path leads to the desired answer. If there are avenues we just never think of, then there are obvious proofs that will never be written, and provable statements that will never be known to be true. The question, then, is whether our machines are subject to the same blind spots. Does the fact that they are built on arithmetic, which is founded on the axioms we set down, and programmed in a way that makes sense to humans, imply that they too will never discover those proofs? (There’s a question about the universality of mathematics in there too somewhere.)

  4. I’m not quite clear to what extent the separation between analytic and synthetic knowledge is productive, or even existent.

    For example,
    1) true assertions about arithmetic are often put forth as archetypical examples of analytic knowledge; and
    2) true (or, I guess more precisely, “approximately true”) assertions about the universe (e.g., quantum mechanics) are often put forth as archetypical examples of synthetic knowledge.

    Indeed, to discover knowledge about arithmetic we seem to not need to leave our comfy armchairs, and yet to discover knowledge about the universe we need to build multi-billion-dollar particle accelerators.

    However, it seems to me that the only difference between the two kinds of knowledge is to what extent are the relevant axioms depending on our taste or not:
    1) in the case of arithmetic, we get to choose what are the axioms of arithmetic for our own convenience, based for example on our physical experience of counting;
    2) in the case of laws of the universe, we don’t get the freedom to choose what are the axioms of nature (i.e., the laws at the basis of everything), and since we are not imaginative enough to guess them, we have to find inspiration through experiments.

    But nonetheless, both arithmetic knowledge and physical knowledge can be derived from axioms in an armchair, *if* the axioms are given to us.

    It’s is just that for arithmetic we get to choose the axioms to serve us well based on everyday experience (which, by the time we sit in an armchair, we have already gone through); and for the universe we need help guessing the axioms since everyday experience only gets us so far in guessing, and then we need to collect more data beyond everyday experience by leaving our armchair and designing complicated experiments.

    Any thoughts?

    • Rudolf Carnap has interesting things to say about this in “Empiricism, Semantics, and Ontology” (http://www.ditext.com/carnap/carnap.html):

      “As an example of a system which is of a logical rather than a factual nature let us take the system of natural numbers. The framework for this system is constructed by introducing into the language new expressions with suitable rules: (1) numerals like “five” and sentence forms like “there are five books on the table”; (2) the general term “number” for the new entities, and sentence forms like “five is a number”; (3) expressions for properties of numbers (e.g. “odd,” “prime”), relations (e.g., “greater than”) and functions (e.g. “plus”), and sentence forms like “two plus three is five”; (4) numerical variables (“m,” “n,” etc.) and quantifiers for universal sentences (“for every n . . . ) and existential sentences (“there is an n such that . . .”) with the customary deductive rules.

      Here again there are internal questions, e.g., “Is there a prime number greater than a hundred?” Here however the answers are found not by empirical investigation based on observations but by logical analysis based on the rules for the new expressions. Therefore the answers are here analytic, i.e., logically true.

      What is now the nature of the philosophical question concerning the existence or reality of numbers? To begin with, there is the internal question which together with the affirmative answer, can be formulated in the new terms, say by “There are numbers” or, more explicitly, “There is an n such that n is a number.” This statement follows from the analytic statement “five is a number” and is therefore itself analytic. Moreover, it is rather trivial (in contradistinction to a statement like “There is a prime number greater than a million which is likewise analytic but far from trivial), because it does not say more than that the new system is not empty; but this is immediately seen from the rule which states that words like “five” are substitutable for the new variables. Therefore nobody who meant the question “Are there numbers?” in the internal sense would either assert or even seriously consider a negative answer. This makes it plausible to assume that those philosophers who treat the question of the existence of numbers as a serious philosophical problem and offer lengthy arguments on either side, do not have in mind the internal question. And indeed, if we were to ask them: “Do you mean the question as to whether the framework of numbers, if we were to accept it, would be found to be empty or not?” they would probably reply: “Not at all; we mean a question prior to the acceptance of the new framework.” They might try to explain what they mean by saying that it is a question of the ontological status of numbers; the question whether or not numbers have a certain metaphysical characteristic called reality (but a kind of ideal reality, different from the material reality of the thing world) or subsistence or status of “independent entities.” Unfortunately, these philosophers have so far not given a formulation of their question in terms of the common scientific language. Therefore our judgment must be that they have not succeeded in giving to the external question and to the possible answers any cognitive content. Unless and until they supply a clear cognitive interpretation, we are justified in our suspicion that their question is a pseudo-question, that is, one disguised in the form of a theoretical question while in fact it is a non-theoretical; in the present case it is the practical problem whether or not to incorporate into the language the new linguistic forms which constitute the framework of numbers.”

  5. bobthebayesian says:

    I find Deutch’s Demon Argument (DDA) to be borderline nonsensical given what Deutsch himself wrote about solipsism in Fabric of Reality. Wikipedia has a nice summary of this:

    “An objection, raised by David Deutsch (among others), is that since the solipsist has no control over the “universe” she is creating for herself, there must be some part of her mind, of which she is not conscious, that is doing the creating. If the solipsist makes her unconscious mind the object of scientific study (e.g. by conducting experiments), she will find that it behaves with the same complexity as the universe described by a realist. Thus what realism calls “the universe”, solipsism calls “one’s unconscious mind.” Understood this way, the distinction between realism and solipsism collapses and amounts to different ways of describing the same thing: a massively complex process that causes all of the solipsist’s experiences, but is not identical to the solipsist’s conscious mind. However despite this the solipsist could still maintain that, unlike Deutsch’s views, that which causes his experiences are still a part of his mind.

    Presumably having made the case that the solipsist scientist is actually a realist scientist, Deutsch next argues in favor of the more common understanding of reality. He applies Occam’s Razor, and suggests that it prefers the standard external ‘reality’ over something like a brain in a vat. This is because the standard ‘reality’ fits all the data available to the scientist, rendering superfluous the other more complicated possibilities.

    If seeking to avoid rejecting the laws of thought, the solipsist may easily appeal to the Problem of Induction. With this he could nullify the use of Occam’s Razor and even Deutsch’s first premises on the solipsists mind, since they are arguments made using inductive reasoning.”

    As Deutsch himself must admit, just from the point of view of simple hypothesis testing, the DDA immediately fails, if it is even falsifiable. We reject it for essentially the same reason we reject creationism. On the other hand, if we presume that this kind of probabilistic reasoning is not meant to apply in the case of DDA, then we might guess this is because Deutsch takes an epistemological approach to mathematical knowledge (i.e. mathematical knowledge is the kind of knowledge that either you are literally certain of or else you cannot claim to “know” it).

    If we take this view (which seems like the only one that doesn’t leave Deutsch looking entirely inconsistent based on the above quote), then it leads us to some sort of mathematical solipsism. Deutch might say something like “I deduce X therefore X is real” instead of “I think therefore I am” and it is just exactly this claim that the demon would be tinkering with. This would seem to deny that something like qualia can have anything to do with mathematical knowledge, but this seems to be at odds with a simple neuroscience point of view that says that at least some part of knowledge is just the plasticity and strength of certain dendritic stumps.

    Ben Best, CEO of the Cryonics Institute (quick! does this make him seem more or less credible to you?) actually has an interesting article that deals with Karl Popper’s views on this briefly. Popper says, “If my opinions are the result of the chemical processes going on in my brain, they are determined by the laws of chemistry, not those of logic.” And then Best offers some analysis:

    “Popper identifies materialism with determinism, but both he and Haldane seem to accept this argument as a self-evident truth, which I would paraphrase “I know I have knowledge, therefore I know I am not determined.” Descartes would be proud.

    But why cannot a material brain have knowledge? If knowledge is an accumulation of synaptic strengths in the brain — as scientific evidence points to — why would the existence of knowledge point to indeterminism, nonmaterial substance or uncaused events (all of which are presumed to be linked to “free choice”)? Effort to form knowledge by choices between explanations seems well within the capabilities of a fully material brain.” I recommend reading the whole article, which could have some interesting things to say about Scott’s recent presentation on free will. The Ben Best article is here: (http://www.benbest.com/philo/freewill.html).

    In general, most philosophers use solipsism as a kind of “proof by contradiction” that certain arguments are bad, and I very much think that this ‘mathematical solipsism’ is a “proof by contradiction” that the DDA is a bad line of reasoning.

    This is becoming long and the original thread running through it is more tenuous now, but I wanted to point out one additional related idea. The relationship with solipsism made me think of a work by David Foster Wallace, “Fate, Time, and Language: An essay on free will” which is a detailed logical counter-argument to Richard Taylor’s work in trying to argue that fatalism (complete ineffectual will, more severe than total determinism) is a syntactic conclusion forced upon us.

    Wallace uses an interesting idea to argue against this, taking Taylor’s famous example of a general giving an order for a battle and explaining why it can be a misconception. He offers two statements (1) “Giving and order means a battle ensues” and (2) “Combustion means the presence of fuel”. In case (1) the battle is a logically necessary consequence of the giving of an order, whereas in (2) the presence of fuel is not a consequence of combustion (unless we don’t believe in time-based causality. I am sympathetic to this and recommend this post: (http://lesswrong.com/lw/r0/thou_art_physics/) ).

    I can’t do justice to Wallace’s description of the relationship between (1), (2), fatalism and metaphysics, so you should read his book. But what was interesting to me is that (1) appears to be a good example of everyday analytic knowledge (under suitable fixed definitions for the words involved) and (2) seems to be more synthetic knowledge (we haven’t observed combustion without the overt presence of fuel, but we have observed combustionless fuel). It would be interesting to investigate further and see if Wallace’s argument does in fact rely on distinctions between these kinds of knowledge.

    • I think that the core of the DDA is not the physcality of our epistemic states, but the decomposability of our reasoning-process into distinct steps. So, like, the force of the DDA is that you never embody a logical proof *at a given time* — you only embody a logical proof over time, and therfore (per Deutsch) to believe that you’re grasping a logical truth is to believe a bunch of contingent truths about what was the physical process the led to your current credal state

      • bobthebayesian says:

        Thanks for the comment, Peli. It did clear up a misconception I was having. However, I think my point might be salvageable. Since one cannot embody a whole proof at a given instance in time, you must rely on the belief that each step in the chain of reasoning that led you to a credal state was valid. I agree with this much. But Deutsch seems to conflate biological credal states (the state of an analog brain) and logical credal states (the position that a proof checker is currently at as it checks a proof, or something similar).

        The quote from Deutsch/Wikipedia about Solipsism reveals Deutsch’s belief that inductive reasoning is an adequate reply to this kind of problem for biological states, i.e. by inductive reasoning you can be assured that it is the universe, and not your own mind, that produces your experiences (according to Deutsch in FoR). Given this, I think Deutsch would be inconsistent to apply the DDA towards a biological credal state like the state of an analog brain. Yes, there could be a demon, but the conjunction of events necessary for the Demon causes the probabilities involved to become fleetingly tiny, much tinier than the probability that my deductive steps were just correctly executed to begin with.

        If Deutsch is to talk about the logical credal state, and in a sense the meta-problem of how would one even do inductive reasoning if the demon were present, then it seems like an epistemic problem about deductive certainity… how can you give an account of “knowing” that a deductive conclusion is certain. If we just go with Deutsch on this, it seems to lead to the kind of mathematical solipsism I mentioned above, which for me is grounds enough to dismiss the DDA.

        Note: I *do not* mean to say Deutsch is “dumb” or something for positing the DDA thought experiment; it’s a good thought experiment but after inspecting his own words, if Deutsch actually buys it as an appropriate biological credal state argument after further thought, that part seems inconsistent to me.

  6. D says:

    The question about the factors of 1591 seems to highlight different senses of the word “know”. There seems to be a continuum of work involved in the effort required to derive a fact; whether or not we “know” a proposition in a casual use of the word depends not just on whether we have sufficient information but also (in effect) our computational resources; how long would it take us to derive the proposition?

    Some things we memorize as facts; if we can immediately recall them, this seems roughly equivalent to taking the statements as axioms. (“Scott Aaronson is the instructor for this class.” “The Pacific is the largest ocean on Earth.”) I don’t have to apply logical reasoning to these facts; I just have to recall them as needed; this is effectively a mental lookup table. Barring a faulty memory, I could say I “know” them. In this sense of “know”, I don’t immediately “know” the prime factors of 1591 (ignoring seeing them in class and in the blog post), though I do “know” the factors of some smaller numbers.

    Some things require a minimal amount of reason, but can still be answered essentially immediately. I might not have been asked for the prime factors of 100000000000000 before, but I could give them immediately since I know a general rule for numbers of that form. The implementation of these simple rules might be as fast as the axiomatic questions; in casual conversation one would likely state that one “knows” propositions of this type as well.

    Then there’s a continuum in which statements one is theoretically capable of deriving from the facts one has available take more and more reasoning to do so. Some of these are solvable practically though not immediately (“multiply these two large random numbers”), some of which might be solvable in a Turing-computable sense though likely not practically (“solve this EXPTIME-complete problem”). In all of these, the answer might not be immediate, but one could readily devise an algorithm to obtain the answer (even if it was inefficient). Here I certainly wouldn’t say the answers are “known”, but there’s some fuzziness at the “easy” end of the spectrum.

    There are other statements in which one doesn’t know an algorithm at all, even if one has the basic axioms. This includes basically any unsolved problem, as well as the wide class of solved problems of which a specific individual is ignorant. In this case we certainly don’t “know” the answer.

    As stated, there’s some ambiguity as to where exactly the line gets drawn; my feeling is that this is inherent due to the word “know” being in casual use. The only way to get a bright-line distinction is to have a formal definition of “know”, but that wouldn’t necessarily capture everything everyone means when they say they “know” something.

    At an informal level, then, I’d say that if I am able to get from my memorized (axiomatic) knowledge to a proposition via a small constant number of rules, then I “know” the proposition. By this definition, I do “know” an infinite number of propositions, since I know induction:
    -I know X
    -By introspection, I know that I know X
    -I know the principle of induction
    -Thus, introspecting on my introspection, I can immediately say that for any n, I know (that I know)^n X.
    I don’t have to make n separate logical steps in my mind; I can mentally short-circuit the process and recognize that by induction this is true for any n. This overall process is simple enough that I’d say that I “know” the proposition for any n (though someone with a very strict definition of “know” might disagree).

  7. Katrina LaCurts says:

    Part of the trouble with defining what we know is that knowing something is tied to how we use it. For example, to know a number implies more than just being able to write it down in some form; it implies being able to use that number in typical ways. In our canonical example with p = 2^43112609 – 1 and q = “next prime larger than p”, I’d say the problem with q is that we can’t use it in the ways we normally expect to use a number we know. However, imagine defining r = “the next Mersenne prime larger than p”. We don’t even know that r exists, whereas we do know that q does. So although I wouldn’t say that I know q in the way I expect to “know” a number, I *would* say that I know it more than I know r.

    Along with tying a person’s knowledge of something with how that knowledge will be use, we also brought up the problem of efficiency. If someone knows a particular fact x, we expect a certain efficiency to go along with that knowledge, e.g., the person should be able to recall x quickly (though I would argue not necessarily immediately). I like D’s version (see above comment) of “know” that includes things I know immediately as well as things I can derive in a small (constant) number of rules, particularly since that includes induction. Interestingly, efficiency alone doesn’t imply knowledge; my computer can look up a variety of facts very quickly, but I would argue that it doesn’t know them (though others might disagree with me).

    It also seems reasonable to answer the question “Do you know x?” with “I don’t know x, but I know how to derive x in a bounded number of steps (perhaps not a small constant)”. Going back to our number example, I don’t know q, but I do know how to derive q in a bounded number of steps; I don’t know how to derive r in a bounded number of steps. Allowing for more than a binary “yes/no” answer to whether I know something seems much more useful.

    Maybe we could get around these problems by being more precise about what we want from someone when we ask them if the know x. Instead of asking “Do you know q?”, I could ask the question “Can you use q in the following ways within a fairly short amount of time after me asking you this question: ..”. I think the latter question is what we really *mean* by knowing the number q, and I’m not sure if it is actually useful to come up with an abstract interpretation of what it means to know a proposition x without tying it to efficiency/how the knowledge will be used (though I’d like to hear from people who disagree!).

    • Katrina LaCurts says:

      Another thing that came up in class that I wanted to mention, but that was somewhat tangential to my original comment was “knowing” that the earth is round. I thought this example was particularly interesting, since “the earth is round” isn’t precisely true. A true fact might be “the shape of the earth can be approximated by a spherical object in many cases”. If we generally take “the earth is round” to be a true fact, it’s because of the second; most of us *use* our knowledge of the earth’s shape in such a way that saying it’s a sphere works out just fine. However, maybe it would be better to classify “the earth is round” as an “approximately true” fact.

      As an aside, I think the “knowledge” of physical objects or constants is interesting, since we typically only know them to the precision that we can measure them.

      • D.R.C. says:

        It’s also a matter of how you are using the objects, not just how precise we can measure them. For instance, if someone just wanted to build a house, then believing the Earth is flat will have the same effect, so it is easier to just assume that it is flat. If you are flying a plane low to the ground, then you will want to know exactly the height of the hills along the flight path. And also, if one is dealing with astronomical scale, a spherical approximation makes more sense for the most part (I suppose low orbit satellites would use obloid approximation, but when dealing with larger scales, spherical would seem to be more efficient). I suppose this could be considered as “approximately true”, or just simply “true for a given purpose”.

        While I like the idea of having a constant number of rules being a metric for whether or not someone knows something, it doesn’t cover the case for generating the next prime q. The algorithm for that simply would need to have the rule to look at only odd numbers, and probably 3 rules for Miller-Rabin with maybe 1 more to determine how many repetitions you need for a desired confidence (and basic arithmetic, I don’t what the deterministic algorithm uses, but since it is a finite test, it must have a finite number of rules, probably not too many). . In addition, this algorithm would be polynomial time (and have a bounded number of steps) assuming the Riemann Hypothesis (I don’t remember if it is the Extended or generalized version). So if we use this rule, we would know q, though I suppose that we would know it “less” than p, because the number rules is a larger constant. Having q be the next Mersenne prime does circumvent this because it they are not know to be an infinite number of them, so while the number of rules is constant, the number of steps is not. An odd case of this idea of “knowing” is how to determine the relative ranking if one thing that we know (call it P1) has fewer rules that need to be know than P2, but a larger bound on the number of steps required. I would suppose this could be viewed as a 2 dimension space, but how to determine the magnitude of the vectors would still be open to interpretations (it would not be surprising there there were multiple “correct” ways of measuring this, this coming up with different orderings of how well be know something, so there would be no canonical ordering of knowledge unless one of the parameters is fixed.

      • Scott says:

        D.R.C.: Unfortunately, it turns out that even assuming the RH or the GRH, we still don’t know that the spacing between two consecutive n-bit primes is polynomial in n (only that it’s at most 2n/2)! To get that the spacing is poly(n), you need a conjecture that looks even stronger than the GRH (though no formal implication appears to be known in either direction), called Cramer’s Conjecture. Obviously, none of this has the slightest effect on the (interesting) real points that you and Katrina were making. 🙂

      • Apropos of nothing, an observation: the number of steps required to calculate both p and q is finite and constant. It’s just that in some sense we “know” the former number, but not the latter. So it seems we’re back to square one — unless the distinguishing factor is simply that the former is less than the latter.

  8. Hagi says:

    I think that most of us did not know that 37 * 43 = 1591, however we knew how to multiply two numbers efficiently. I imagine that “knowing how” and “knowing that” can be equally fundamental, as we can store compressions of facts and algorithms in our brains using neurons; just like a computer can use the same bits to effectively store data or program instructions. In this sense, I do not think it is possible to know that 37 * 43 = 1591, but not know the prime factors of 1591. However, we do know how to multiply these two numbers faster than finding the prime factors of 1591. Again following this logic, we do not know an infinite number of propositions, however we have several algorithms that would allow us to learn infinite number of propositions given infinite time and memory, however unfortunately we do not have that much time.

    Regarding the analytic – synthetic knowledge distinction: Similar to many other questions we faced in this class, I think the answer is that there is a spectrum and different propositions live in different parts of this spectrum. The proposition “All bachelors are unmarried.” is much closer to the analytic end; however, the proposition that “All bachelors are unhappy.” is much farther. It can still be analytic in some sense though, since given a powerful enough computer, one could simulate a world in which humans have evolved and within this framework being a bachelor had to come with certain psychological burden. We can define how analytic or synthetic a proposal is given what resources it would take to reach that conclusion using the subject concept.

  9. kasittig says:

    The field of artificial intelligence appears to entirely revolve around developing systems that know how rather than know what, a problem that appears to be far more difficult than we perhaps originally anticipated. Consider Watson, for instance, who gave an extremely impressive performance on Jeopardy! but who was criticized for not actually being an “intelligent” system. Watson was a fantastic example of a system that knew a lot of “what” – in spite of some of his failures, he was still an extremely impressive competitor – but logical reasoning definitely appeared to be beyond Watson.

    Deep Blue, however, can be argued to have at least somewhat known how to play chess – and yet, that was all it “knew” how to do. While Deep Blue had significantly less computational power than Watson, and while arguably computer science has come a long way since Deep Blue was built, Deep Blue still appears to have solved a much “smaller” problem than Watson (as Watson can supposedly be generalized to answer questions on any topic, where Deep Blue can only play chess).

    It’s interesting then that machine learning appears to have transformed into systems that attempt to know what, rather than know how – binary classifiers, for instance, are a huge area of study. While this may imply that knowing what is more interesting or more relevant than knowing how, I’d argue that it’s actually the opposite – knowing how is far, far more difficult than knowing what.

    I think the core difficulty rests with the fact that, in order to know what, someone has to know how in order to arrive at that information in the first place, and therefore, in order to be able to articulate and program a machine that would be able to know “how” in a general sense, we would need a better understanding of our own thought processes that simply isn’t there yet. How we should get this information, however, is still up for debate.

  10. nemion says:

    I was particularly puzzled with the following issue that was discussed during the last lecture:

    Is logic empirical?

    Logic and mathematics allow us to make inferences (at least observationally verifiable) on the real world. If logic were empirically derived, it would imply that there exists some relation between the empirically derived inference rules and the fundamental structure of reality. It seems fair to ask the following question: why is it that our inference rules work? Why there seems exist imply some degree of self consistency in our empirical knowledge (at least observationally)?

    We can think of the following solutions of this question, namely, logic and all inference rules we use for predicting outcomes in the real are given (maybe not given?) principles that we came to know due to evolution, they would therefore be statistically verified inference rules that have helped our species and our ancestors to make sense of reality, and that therefore the edifice of all our inferential knowledge (and this includes science) is not based on anything, but is a self sustaining monster that sometimes challenges a bit of itself and changes it. But if that is the case, is there actually a base justification any type of conclusion we draw from them? Are the conclusions that I am drawing even in this argument thus derived empirically if I am using the language of logic?What is then the foundation of our inferential rules, and our inferential knowledge of the world? Can it be actually justified?

    Our boolean logic doesn’t seem to serve to predict the consequences of a quantum environment, (i.e. if we were quantum beings we would have probably came up with another type of logic). In particular, our boolean logic seems to draw from the perceptual given that 2 things cannot superimpose, and furthermore, logic itself seems to be a given (or at least some sort of early apprehended given. No one learns formal logic before being able to make sense of mathematical proofs). If this is the case, wouldn’t then mathematics, that relies on this empirical / given base be not more than a language (i.e. the difference between ma±thematics and English would be in degree but not in kind) and its inference rules, a type of grammar. Then how do we make sense of the quantum logic possibility? Our answer could take the following paths:

    Our empirical derived grammar for reality breaks in extraneous domains as quantum (or others?), or it could be that we must incur in some “translation costs” from one grammar to the other. If that is the case, then our grammar for describing the world (whatever this might be) is bounded to our perceptual realm, due to a complexity cost in going down or up the spiral of descriptive realms. Is it then that we can come up with a descriptive grammar up to translation costs? Are these translation costs the justification of its adequacy, of its empirical results?

  11. I want to make the claim that degree of “knowledge” is entirely dependent on the the context in which you intend to use that knowledge. Knowing the decimal expansion of a number lets us answer many more questions about that number than simply knowing it exists. In particular, it lets us answer many more questions within a reasonable amount of time.

    It doesn’t make sense to talk about knowing something or not — you can ask whether someone can answer a question about a thing correctly or not, but we don’t have any way of expressing some platonic ideal of “knowledge”.

    This may seem pedantic or onerous but it’s not — it’s important to realize that whenever we make a statement (like, “The Earth is round”) we are making it in a certain context and with certain assumptions. Luckily we have converged enough on those contexts and assumptions that we can hold reasonable conversations and get things done. But this is a happy accident, not a mandated rule.

  12. amosw says:

    Regarding Zero-Knowledge proofs and their implicit physical
    assumptions: I wonder if we shouldn’t be a bit more cautious about
    assertions of the form “Arthur learns nothing from the protocol
    beyond the truth of the statement being proved.” This seems
    similar to asserting that an information channel has zero
    capacity: which doesn’t seem to me in general an easy thing to prove.

    Let us suppose we have two parties A and B.

    A is Aaronson, who has discovered a truly wonderful algorithm that can
    detect in polynomial time when graphs G and H of the same degree
    are not isomorphic.

    B is … the NIPS program committee.

    Now, A wishes to convince B that he has the algorithm, but he doesn’t
    want to explicitly show the algorithm to B because he intends to make
    heaps of money off of it via currency graph forex arbitrage.

    Next, suppose the program committee chair is clever, and that cost being
    no object, she sets up an interactive proof session in which A is
    spatially separated from B by 1 light minute. Under current physical
    assumptions, the minimum reply time in their session is then 2 minutes.
    I’d like to suggest that in this scenario it would be very difficult
    for A to ensure that B gets ZERO bits of information from their session.

    For example, if A were not aware that he is under an attack that
    is attempting to learn the leading power of the polynomial that describes
    his algorithm’s scaling, he might answer as quickly as he can to a
    sequence of queries involving graphs of degree 1000, 1001, …
    His answers come back in 2 + f(1000), 2 + f(1001), … seconds.
    In this case, B now knows a bound on A’s action in the foreign exchange
    markets and can in principle trade into him, actually making more
    money than he does!

    In summary, I am not doubting the utility of Zero-Knowledge proofs,
    I am only wondering whether they are truly “zero”, as opposed to
    “very limited”, knowledge proofs.

    • Scott says:

      Amos: I love your thought experiment! And it raises an important issue, which (as you might know) is a big topic in current cryptography research. Namely, there are many, many cryptosystems that are “provably secure” under some plausible complexity assumption, but that become insecure if you violate the assumptions of the model — for example, by executing a “timing attack” where you measure the amount of time some party needs to do a computation, or an attack where you measure the radiation emanating from that party’s computer, or how much power they’re consuming, or something like that.

      Furthermore, my understanding is that when modern cryptosystems have been broken, it’s almost never been by “bashing down the front door,” so to speak (that is, violating whatever mathematical assumption the cryptographers thought they were making), but rather by finding some “side door” that the cryptographers never even considered.

      All that is true, but there’s still an interesting sense in which protocols like the one for Graph Non-Isomorphism are zero-knowledge — indeed, provably zero-knowledge. (Although unfortunately, we didn’t do the proofs in class — you’ll need to take the grad crypto class for that.) Namely, if the verifier has no other information channels than the ones explicitly described in the protocol, then in probabilistic polynomial time, the verifier can simulate the entire interaction on its own.

      What often happens in practice is that, when crypto researchers write a paper, they’re careful to state the conditions under which their system is secure — then someone implements the system in a way that violates those conditions — then the system is broken, and people blame the original researchers! 🙂 (Though if the researchers wrote things that were true but misleading, then arguably they do bear some blame…)

  13. beast says:

    I want to consider a very specific type of knowledge. One where you cannot truly ‘know’ a piece of knowledge x if you know the piece of knowledge y – i.e. the ability to know something is dependent on not knowing something else. In addition, in the following discussion I present an example of this type of knowledge where x is the ‘same’ knowledge as y except that x is a statement and y is an understanding of a system that leads to the assertion and validation of x.

    One can find an instance of this type of knowledge in Hindu philosophy. Consider an parallel analogy of this instance first. Conceive of a conscious ocean [god] that is tasked with realizing that it is one body of water. If it takes on the divide and conquer approach, it separates itself into individual drops [individual egos… humans etc.] that look around themselves and make sure that they are connected to the drops around them. In this separation, the ocean loses the knowledge of it being one entity as the individual drops must take on their own perspective… essentially forgetting that they are all actually the same water. Looking at a drop in the ocean is still looking at the ocean, but the drop thinks its different until it realizes that its just the same water. Consequently, this is the type of knowledge I specified earlier: the ocean cannot know (in the sense of knowing a fact [what]) that it is one entity at the same time as it knows (in the sense of experiencing and discovering a fact [how]) that it is one entity.

    Alright, now for the actual instance. Hindu philosophy – specifically the Advaita Vedanta school of thought – asserts [or at least what I think it asserts] that there is one entity in this and all universes. This one entity is god and everything is a part of god. It says that the god goes through cycles of going from knowing fact x – that it is one entity – to forgetting fact x in order to know piece of knowledge y – the state of the universe is such that it is not actually separated and one entity which leads to fact x. Regardless of whether one believes this assertion from Hindu philosophy, just conceiving such a form of knowledge is an interesting consideration.

    I do understand that this might have been a very complicated expression of this example, but I tried hard to simplify it 🙂

    Let me know if I can clarify it more to spur some debate on the topic!

  14. Miguel says:

    Consider the following informal setup, borrowed from GWI’s seminal 1985 paper: imagine a crime x being investigated by a police officer A1 and an FBI detective A2, who has just arrived to the scene in order to be briefed (and so knows nothing about x).

    Now, assume that both A1 and A2 receive an urgent order from, say, Homeland Security, to immediately send a report on x to some unknown and busy higher-up B, based only on whatever they ‘know’ at that moment. One would expect A2 will have a much more difficult time than A1 in producing the report, because (we presume) A1 knows a lot more about the crime than A2, who has just arrived in the scene. Another way to state this is that the probability that A1 will produce a coherent report on x will be much, much higher than A2’s, who will have to essentially make stuff up.

    Now, assume that A1 and A2 are able to talk to each other about the crime as they submit their respective reports. Since A2 doesn’t want to lose her job, she will ask A1 as many questions as she can about the crime so that, after a large enough number of queries, she will be able to file a report about x just as well as A1. One would also expect that the less A2 knows about the crime, the larger the number of queries to A1 she will require. So it seems that the more a ‘knowledgeable’ agent ‘knows’ about something, the harder it is for `dumb’ agents to replicate their behavior by just querying them.

    So, at risk of putting forward a triviality, consider the following measure of knowledge (modified from Goldreich 1996, also GWI 1985): a Turing machine A that accepts some input x efficiently possesses at most k(|x|) bits of knowledge about x (with k non-decreasing) if there exists an oracle W and poly-time Turing machine M such that M^W can efficiently simulate A by making at most k(|x|) queries to W. Similarly, A has k knowledge of a language L if, on all inputs x in L, A possesses at most k(|x|) bits of knowledge about x. Alternatively one could require that A be a prover in an interactive proof, so that the challenge of M is to efficiently simulate A’s proof to some poly-time verifier B. The motivation is to model the fact that the more A knows about a problem, the harder it is for some ‘dumb’ machine M to simulate A via cheating (by, say, checking Wikipedia). Also note that k is just a proxy for the complexity of A, so the harder the problem A is able to compute efficiently, the higher the upper bound on the number of queries M will have to make.

    This account of knowledge as “knowing how” I believe explains some of the gray areas of knowledge discussed so far. As stated in class, a ‘dumb’ agent that can efficiently compute functions in, say, AC0 but not in NP-complete will very efficiently decide some infinite families of simple arithmetic problems (e.g. facts that will ‘spring immediately to mind’); some others less so (e.g. facts that ‘require contemplation’); and unfeasibly some others (e.g. unknown facts), without contradiction. More interestingly, the computational advantage gained by access to an oracle might be a good model for explaining how propositional knowledge might depend on experience or information outside the ‘subject concept’: `a posteriori’ or `synthetic’ propositions might correspond to statements that can only be feasibly computed by an agent after querying an oracle about the respective ‘meta’ facts (e.g. Facts of experience, or propositions not efficiently inferable from the statement itself). The fact that knowledge seems to depend on the types of questions being asked can also be seen as a result of slightly different computational capacities: an agent that is able to efficiently compute a function only after a brief query to an oracle (for instance a hint) is only slightly less ‘knowledgeable’ than an agent that can do so without the oracle, which is compatible with one’s intuition that variations in the ‘form’ of questions within a specific family of problems ought not to have much of an effect on the extent of an agent’s knowledge that one is trying to infer.

  15. Cuellar says:

    There is a strong ambiguity in the common use of the word knowledge. Notice that if I tell you today that 37×43=1591 and tomorrow I ask you if you know the prime factors of 1591, you would probably forget our previous conversation and say ‘No’. On the other hand if I ask you about the proof of the undecidability of halting problem you would say ‘Yes’, though you probably don´t have it all memorized.

    So, Is it possible to “know” that 37×43=1591, yet not “know” the prime factors of 1591?
    The answer should be, Yes and no. When we are told that 37×43=1591, we stored it in our explicit knowledge. On the other hand, if we have never asked about the prime decomposition of 1591, we don´t have that fact in our explicit knowledge and hence we DON’T know it–in that sense. Nevertheless, the prime factors of 1591 are easily inferred from our explicit knowledge, so it is part of our implicit knowledge. Other things in our implicit knowledge are proofs, for which we know the sketch and we can complete in our minds. So, for example, it is impossible to have infinitely propositions in our explicit knowledge, but and explicit knowledge can generate infinitely implicit statements.

    So how is it possible that you said you didn’t know the prime factorization of 1591 when it was on your explicit knowledge? Well it is normal to know something and be unaware of it. For example, Luke meets Darth Vader and yet he is unaware that he knows his father. I think this is a loose answer to the problem of accessibility that Stalkner presents. I think we can be unaware of their of parts of our implicit and explicit knowledge without loosing the ‘capacity’ that that knowledge gives you.

    What about the problem of Logical Omniscience? There are levels of ‘knowing’ in our implicit knowledge. We commonly say:
    -“Do you know the proof for _?”
    -“More or less.”
    That is because we estimate that the proof should be in our implicit knowledge but it’s somewhat hard to compute it. The common use of ‘know’ implies and easy derivation from the explicit knowledge although this limit is not well defined–and it does not have to be!

  16. wjarjoui says:

    Regarding mathematical proofs and their relation to physical reality –

    As Deutch argues that mathematical proof is absolutly dependable on physics, it does not seem he is necessarily refuting the opposite of that argument. Deutch’s argument relies on the fact that when we accept a proof, we do so while implicitly making assumptions about the phsyical reality – for example, that a demon isn’t changing on a page of the proof after we read it. However, while that’s true, does it imply that there can’t exist a proof that does not require us to make such assumptions?

    Deutch argues that such a proof would be entirely abstract, and meaningless. However, perhaps thare are deeper universal laws of physics that we are not yet acquainted with that allow us to prove mathematical statements independently of sub-universal laws of phyiscs. But then perhaps there are even super-universal laws of phyiscs (encompassing universal laws of phyiscs for each universe perhaps) and then mathematical statements can be proven with ‘more’ abstraction, and it would seem that this is an infinte regress. Hence does not seem very fruitful to follow the line of path Deutch is arguing against, but it is important to give it a thought at least – I’ll be happy to hear what someone else has to say about this, perhaps this line of thought can be expanded in a fruitful way.

    In any case, it is also important to not that Deutch uses the second notion of a proof as described in WPSCACC Sec 9, which raises the question of what would his argument be for the other proof protocols regarding their dependence on physical reality. For example it seems that first notion of proof described in WPSCACC does not necessarily have to depend on physical reality. A notion of certainty could be established without precisely following a series of computations based on physical laws, rather it would be more of an “abstract understanding’ – something that Deutch argues is not enough to build a proof. But I guess that depends on the defintion of proof being used!

    • bobthebayesian says:

      I like your ideas, but I am curious what you think about Cox’s theorem. The Field’s medalist David Mumford described this theorem: “We may summarize this result as saying that probabilities are the normative theory of plausibility, i.e., if we enforce natural rules of internal consistency on any homespun idea of plausibility, we end up with a true probability model” [link].

      Some have argued that Cox’s theorem and things like the maximum entropy principle make probability theory the unique framework for mathematical inference from data, and further that these ideas are physically motivated. Do you reject this idea in favor of other interpretations of probability? If someone accepts this idea, then for them must probabilistic proofs ultimately depend on physical laws (in some manner more interesting that just superficial probabilities (i.e. things like cosmic ray bit flips don’t need to be considered))? I think it presents an interesting chicken and egg problem. Is probability given to us by physics or do we determine physics by using separately axiomatized probability?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s