User dfranke - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T21:08:48Z http://mathoverflow.net/feeds/user/8272 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/40005/generalizing-a-problem-to-make-it-easier/40354#40354 Answer by dfranke for Generalizing a problem to make it easier dfranke 2010-09-28T17:58:26Z 2010-09-28T17:58:26Z <p>Bruce Schneier has an online paper called "A Self-Study Course in Block-Cipher Cryptanalysis": <a href="http://www.schneier.com/paper-self-study.pdf" rel="nofollow">http://www.schneier.com/paper-self-study.pdf</a> containing an extensive list of algorithms to cryptanalyze as exercises. By far the easiest exercise is this one:</p> <blockquote> <p>[Cryptanalyze] a generic cipher that is “closed” (i.e., encrypting with key A and then key B is the same as encrypting with key C, for all keys).</p> </blockquote> <p>The solution to this exercise would be a lot less obvious had Schneier instead pointed to some particular block cipher that has this property. But because the reader is told nothing about the cipher except that it is closed, he immediately knows exactly what to attack.</p> http://mathoverflow.net/questions/39783/number-of-ways-to-construct-mathematical-objects/39784#39784 Answer by dfranke for Number of ways to construct mathematical objects dfranke 2010-09-23T18:58:55Z 2010-09-23T20:45:31Z <p>How about models of computation?</p> <ul> <li>Turing machines</li> <li>Register machines</li> <li>Cellular automata</li> <li>$\mu$-recursive functions</li> <li>The untyped $\lambda$-calculus</li> <li>Unrestricted grammars</li> <li>Term-rewriting systems</li> <li>Recursively-enumerable subsets of $\mathbb{N}$</li> <li>$\ldots$</li> </ul> <p>To this list we can add finite presentations of semigroups and groups, diophantine sets, and many other mathematical structures that realize universal computation.</p> http://mathoverflow.net/questions/39626/is-there-a-general-setting-for-self-reference/39629#39629 Answer by dfranke for Is there a general setting for self-reference? dfranke 2010-09-22T15:50:32Z 2010-09-22T15:50:32Z <p>Perhaps the right question to ask is if the statement is expressible in any system whose proof-theoretic ordinal is smaller than the Feferman–Schütte ordinal.</p> http://mathoverflow.net/questions/38856/jokes-in-the-sense-of-littlewood-examples/38902#38902 Answer by dfranke for Jokes in the sense of Littlewood: examples? dfranke 2010-09-16T00:44:54Z 2010-09-16T00:44:54Z <p>Hausdorff dimension. Try showing a Sierpinski triangle to a non-mathematician and explaining that it is a 1.585-dimensional object.</p> http://mathoverflow.net/questions/35461/interesting-complexity-classes-pr-subsetneq-c-subsetneq-r Interesting complexity classes $PR \subsetneq c \subsetneq R$ dfranke 2010-08-13T09:48:27Z 2010-08-13T14:01:12Z <p>I'm working on a proof-checker that can verify termination proofs. The fundamental method it provides for constructing such proofs is to translate the program into primitive recursion. Basically, I provide a combinator $\rho$ typed as:</p> <p>$\rho: \forall A,B:(A\rightarrow Nat \rightarrow A)\rightarrow (A \rightarrow B)\rightarrow A\rightarrow Nat \rightarrow B$</p> <p>which, in the notation defined <a href="http://en.wikipedia.org/wiki/Primitive_recursion" rel="nofollow">here</a>, constructs $h$ given $f$ and $g$.</p> <p>Although the term language contains a fixed-point combinator and is therefore Turing-complete, terms that use it have a "tentative" flag in their type that indicate this. The $\rho$ combinator and the fixed-point combinator are the only two language primitives that allow for recursion or looping of any sort (i.e., without either of these two combinators, all you've got is a finite-state machine). Therefore, all terms that are well-typed and non-tentatively typed are primitive recursive.</p> <p>What I'm wondering is if there are any interesting complexity classes that you can build by starting with primitive-recursive constructions, and adding a finite number of other functions $Nat \rightarrow Nat$, each of which is in R but not in PR, and allowing composition with these functions. It's easy to come up with <em>non</em>-interesting examples of such classes, e.g. "primitive recursion plus the Ackermann function", but I'm looking for any that have sufficiently interesting properties that it would be worth adding the functions which characterize them as admitted axioms in the proof system.</p> http://mathoverflow.net/questions/39626/is-there-a-general-setting-for-self-reference/39629#39629 Comment by dfranke dfranke 2010-09-22T16:18:44Z 2010-09-22T16:18:44Z I think that before I can make a more rigorous proposal about what a self-referential statement is, we first need to set boundaries on what qualifies as a statement. If we need to take into account such sentences as &quot;colorless green ideas sleep furiously&quot;, then I wouldn't know where to begin. http://mathoverflow.net/questions/35461/interesting-complexity-classes-pr-subsetneq-c-subsetneq-r/35495#35495 Comment by dfranke dfranke 2010-08-15T15:33:17Z 2010-08-15T15:33:17Z Alright, I get it now. What I was missing before was the essentialness of encoding natural numbers as iterator functions. That's where you get the &quot;potential energy&quot;, so to speak, in order to compute complex functions without the need for a recursion operator. Thanks again. http://mathoverflow.net/questions/35461/interesting-complexity-classes-pr-subsetneq-c-subsetneq-r/35495#35495 Comment by dfranke dfranke 2010-08-13T14:35:10Z 2010-08-13T14:35:10Z Nifty. So the answer is that I don't even need $\rho$ as an axiom: the underlying system is already expressive enough to construct it and much more beyond it, and I need to finish wrapping my brain around the properties of that system. http://mathoverflow.net/questions/35461/interesting-complexity-classes-pr-subsetneq-c-subsetneq-r Comment by dfranke dfranke 2010-08-13T14:03:13Z 2010-08-13T14:03:13Z No problem. Done. http://mathoverflow.net/questions/35461/interesting-complexity-classes-pr-subsetneq-c-subsetneq-r Comment by dfranke dfranke 2010-08-13T12:53:19Z 2010-08-13T12:53:19Z So, to rephrase my question without having to go into the gory details of the type calculus: can you get any interesting complexity classes by starting with a system that permits only primitive-recursive constructions, and augmenting it with certain $Nat \rightarrow Nat$ total functions that are not in PR. http://mathoverflow.net/questions/35461/interesting-complexity-classes-pr-subsetneq-c-subsetneq-r Comment by dfranke dfranke 2010-08-13T12:50:00Z 2010-08-13T12:50:00Z ...right, which is what I get for trying to ask coherent math questions at 5:30 AM. The system I'm working in is one based on Luo's Extended Calculus of Constructions. It contains a fixed-point combinator in addition to the above $\rho$ combinator and therefore <i>is</i> Turing-complete, but expressions that invoke it have their types flagged to indicate that they do. But, every well-typed term that is not so-flagged is in PR, because $\rho$ is the only other combinator that provides recursion.