User antonio e. porreca - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T22:11:07Z http://mathoverflow.net/feeds/user/5304 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/69337/what-is-some-good-introduction-to-lambda-calculus/69356#69356 Answer by Antonio E. Porreca for What is some good introduction to lambda calculus? Antonio E. Porreca 2011-07-02T19:32:39Z 2011-07-02T19:32:39Z <p>An introductory book that seems very nice to me is <a href="http://www.cambridge.org/gb/knowledge/isbn/item1175709" rel="nofollow"><em>Lambda-Calculus and Combinators. An introduction</em></a> by J. Roger Hindley and Jonathan P. Seldin.</p> http://mathoverflow.net/questions/30808/has-there-ever-been-a-weaker-church-like-thesis Has there ever been a weaker Church-like thesis? Antonio E. Porreca 2010-07-06T19:38:49Z 2011-02-18T04:14:55Z <p><strong>Background.</strong> The <a href="http://en.wikipedia.org/wiki/Church-Turing_thesis" rel="nofollow">Church-Turing thesis</a>, in one of its many equivalent formulations, states that the intuitively computable arithmetical functions are exactly those computed by Turing machines.</p> <p>According to Alan Turing’s classic paper <a href="http://plms.oxfordjournals.org/cgi/pdf_extract/s2-42/1/230" rel="nofollow">On computable numbers, with an application to the Entscheidungsproblem</a>, “intuitively computable” refers to a human computer having access to enough scratch paper to hold the intermediate results.</p> <p>This thesis has been extremely successful among logicians first (including <a href="http://books.google.com/books?id=qW8x7sQ4JXgC&amp;pg=PA72" rel="nofollow">Kurt Gödel</a>), and computer scientists later; some authors even extended it to include all functions that can be computed by any <a href="http://bjps.oxfordjournals.org/cgi/content/abstract/54/2/181" rel="nofollow">effectively realizable physical system</a>.</p> <p>Nonetheless, the Church-Turing thesis is, at least in principle, falsifiable: it is enough to describe a non Turing-computable function admitting another kind of computation procedure, executable by the above-mentioned human computer. Of course, no such function is known to exist; however, consider the following “weaker computability thesis” for the sake of argument:</p> <blockquote> <p>Every intuitively computable arithmetical function is <a href="http://en.wikipedia.org/wiki/Primitive_recursive_function" rel="nofollow">primitive recursive</a>.</p> </blockquote> <p>This is falsified by <a href="http://en.wikipedia.org/wiki/Ackermann_function" rel="nofollow">Ackermann's function</a>, which is clearly computable (both intuitively and by a Turing machine) although not primitive recursive.</p> <p><strong>Question.</strong> Has a similar, provably weaker “computability thesis” ever been proposed before Church’s and Turing’s? As an alternative, can we reasonably argue that no such statement was ever made?</p> http://mathoverflow.net/questions/38460/arithmetic-of-ordered-sets-more-general-than-ordinals Arithmetic of ordered sets more general than ordinals Antonio E. Porreca 2010-09-12T10:04:32Z 2010-09-13T02:14:21Z <p><b>Motivation.</b> Having read about <a href="http://dx.doi.org/10.1023/A:1021180801870" rel="nofollow">infinite time Turing machines</a> and <a href="http://en.wikipedia.org/wiki/Omega_language" rel="nofollow"><i>&omega;</i>-languages</a>, I was thinking about more general notions of languages and “computation time”. Languages over strings of length greater than <i>&omega;</i> seem reasonably easy to define, and using larger ordinals to measure time is quite standard.</p> <p>However, I’m interested in more general, non necessarily well-founded ordered sets. Using ordered sets to keep track of time seems to require suitable notions of arithmetic operations. For example, it’s easy to generalise sum and multiplication of ordinals to arbitrary totally ordered sets (though, of course, these operations are not defined by transfinite recursion); I’m not sure about exponentiation and other operations.</p> <p><b>Question.</b> Is there any good literature about arithmetic of (some classes of) non well-founded ordered sets?</p> http://mathoverflow.net/questions/35461/interesting-complexity-classes-pr-subsetneq-c-subsetneq-r/35495#35495 Answer by Antonio E. Porreca for Interesting complexity classes $PR \subsetneq c \subsetneq R$ Antonio E. Porreca 2010-08-13T14:01:02Z 2010-08-13T14:01:02Z <p>First of all, it’s certainly possible to obtain <em>some</em> intermediate class by taking a language that only computes PR functions (say, an imperative programming language <a href="http://en.wikipedia.org/wiki/BlooP_and_FlooP" rel="nofollow">using only <code>for</code> loops</a>) and adding any total computable but non PR function (e.g., Ackermann’s function). The resulting language <em>L</em> is non-universal, because it only computes total functions: you can still construct a computable but non-<em>L</em>-computable function by diagonalisation. However, <em>L</em> is clearly more powerful than the original language.</p> <p>As for “interesting”, I guess it really depends on what you mean by that.</p> <p>If “interesting” means “of practical use”, then one could answer that all computable functions of practical use are PR, since a non-PR function requires an amount of time to compute that is not, in turn, PR. Considering that time bounds such as 2<sup><em>n</em></sup>, 2<sup><em>2</em><sup><em>n</em></sup></sup>, 2<sup><em>2</em><sup><em>2<sup><em>n</em></sup></em></sup></sup>, …, are all PR, you see that there isn’t much hope to compute non-PR functions for large values of <em>n</em>.</p> <p>If “interesting” means “logically interesting”, then I think the answer is “yes”. I’m somewhat familiar with Girard’s System F (also called “second order λ-calculus” or “polymorphic λ-calculus”), described for instance in Girard’s <em>Proofs and Types</em> (freely available <a href="http://www.paultaylor.eu/stable/Proofs+Types.html" rel="nofollow">here</a>). The functions that can be computed in F are “<em>exactly</em> those which are provably total in [second order Peano arithmetic]” (page 123), and among these we have Ackermann’s function. There is an explicit λ-term for it on <a href="http://www.pps.jussieu.fr/~miquel/enseignement/mpri/SystF.pdf" rel="nofollow">these slides</a> (page 20).</p> <p>If I recall correctly, the standard calculus of constructions includes System F and only computes total functions, so it also provides an example.</p> http://mathoverflow.net/questions/35401/post-correspondence-problem/35403#35403 Answer by Antonio E. Porreca for post correspondence problem Antonio E. Porreca 2010-08-12T23:03:56Z 2010-08-13T01:18:25Z <p>As Tsuyoshi said, it doesn’t make sense to search for an undecidable <em>instance</em> of a problem. It’s only the <em>problem</em> itself that can be undecidable.</p> <p>In particular, for <em>every</em> instance of PCP (or any other problem for that matter) there trivially exists an algorithm that gives the correct answer for that particular instance. If we’re dealing with the decision version of the problem, it’s either the algorithm that always answers “yes”, or the algorithm that always answers “no” (granted, this is not a constructive proof).</p> <p>On the other hand, you might find specific instances of PCP without a <em>known</em> answer, for example by exploiting any open problem of mathematics and the fact that the halting problem reduces to PCP, say via a many-one reduction <em>R</em>.</p> <p>Consider the Turing machine <em>M</em> that searches for a proof of the Riemann hypothesis by enumerating all proofs, and halts when it finds it. If RH is provable, this machine will halt in a finite amount of time, otherwise it will run forever. You can use the reduction from the halting problem to construct a PCP instance <em>R</em>(<i>M</i>) = <em>x</em>. Now, by deciding whether <em>x</em> is a positive or negative instance of PCP, you also decide RH. But that’s an open problem, and so the status of <em>x</em> also is.</p> http://mathoverflow.net/questions/34099/the-best-text-to-study-both-incompleteness-theorems/34102#34102 Answer by Antonio E. Porreca for The best text to study both incompleteness theorems Antonio E. Porreca 2010-08-01T11:29:47Z 2010-08-01T11:29:47Z <p>Speaking as a beginner myself:</p> <p>I haven’t read it all yet, but <a href="http://www.logicmatters.net/igt/" rel="nofollow">An Introduction to Gödel’s Theorems</a> by Peter Smith seems like a good candidate, and it doesn’t have many prerequisites. Smith also wrote a series of shorter handouts on the topic, <a href="http://www.logicmatters.net/igt/godel-without-tears/" rel="nofollow">Gödel Without (Too Many) Tears</a>.</p> <p>There’s also <a href="http://www.amazon.com/Godels-Theorem-Incomplete-Guide-Abuse/dp/1568812388/" rel="nofollow">Godel’s Theorem: An Incomplete Guide to Its Use and Abuse</a> by Torkel Franzén, which is much less technical and primarily concerns false myths about the incompleteness theorems; in my opinion, it is a good companion (not a substitute) for Smith’s book.</p> http://mathoverflow.net/questions/31893/what-is-the-history-of-the-y-combinator/31901#31901 Answer by Antonio E. Porreca for What is the history of the Y-combinator? Antonio E. Porreca 2010-07-14T19:54:24Z 2010-07-14T19:54:24Z <p>The paper <a href="http://www-maths.swan.ac.uk/staff/jrh/papers/JRHHislamWeb.pdf" rel="nofollow">History of Lambda-calculus and combinatory logic</a> by F. Cardone and J.R. Hindley is a good starting point for answering such a question, and many others (it has 38 pages of bibliography). There’s a brief account on fixed-point combinators on page 8, although it doesn’t seem to settle the question completely.</p> http://mathoverflow.net/questions/31733/can-i-have-an-ll-grammar-for-every-deterministic-context-free-language/31746#31746 Answer by Antonio E. Porreca for Can I have an LL grammar for every deterministic context free language? Antonio E. Porreca 2010-07-13T18:47:38Z 2010-07-13T19:17:28Z <p>I’m not an expert on this topic, but I found these <a href="http://www.gdi.uni-bamberg.de/teaching/SS10/GdI-GTI-B/tomlect8.pdf" rel="nofollow">course notes</a> (including some bibliographical references) which state that the language <i>L</i> = {<i>x<sup>n</sup></i> : <i>n</i> &isin; &#8469;} &cup; {<i>x<sup>n</sup>y<sup>n</sup></i> : <i>n</i> &isin; &#8469;} has no LL(<i>k</i>) parser, while being deterministic context-free (see pp. 24 and 27).</p> <p>Edit: I found a better reference. The paper <a href="http://www.cs.uwaterloo.ca/research/tr/1978/CS-78-24.pdf" rel="nofollow">Two iteration theorems for the LL(<i>k</i>) languages</a> by J.C. Beatty contains a proof that the LR language <i>L</i> = {<i>a<sup>n</sup>b<sup>n</sup></i>, <i>a<sup>n</sup>c<sup>n</sup></i> : <i>n</i> &ge; 1} is not LL (see Theorem 5.2).</p> http://mathoverflow.net/questions/31448/lower-bounds-in-theoretical-computer-science/31465#31465 Answer by Antonio E. Porreca for Lower Bounds in Theoretical Computer Science Antonio E. Porreca 2010-07-11T21:08:17Z 2010-07-11T21:08:17Z <p>No <b>EXPTIME</b>-complete problem can be solved in polynomial time as a consequence of the <a href="http://en.wikipedia.org/wiki/Time_hierarchy_theorem" rel="nofollow">time hierarchy theorem</a>. Of course, the same holds for harder problems, such as problems complete for exponential space, doubly exponential time, etc. These results are unconditional (i.e., they do not depend on <b>P</b> &ne; <b>NP</b> or other conjectures).</p> <p>There are some interesting problems which provably lie outside <b>P</b>; one of them concerns the equivalence of regular expressions (see these <a href="http://diuf.unifr.ch/tcs/seminars/seminarSS05/beyondNP.pdf" rel="nofollow">slides</a> for an introduction), and <a href="http://en.wikipedia.org/wiki/Generalized_game" rel="nofollow">some kinds of game</a> are also very hard to solve.</p> http://mathoverflow.net/questions/27572/are-there-complexity-classes-with-provably-no-complete-problems/27612#27612 Answer by Antonio E. Porreca for Are there complexity classes with provably no complete problems? Antonio E. Porreca 2010-06-09T19:39:12Z 2010-06-09T19:39:12Z <p>Another class without complete problems w.r.t. logspace or polytime reductions (not an union of classes <b>TIME</b>(<i>f</i>) for some family of polynomially related functions <i>f</i>, but still relatively natural in my opinion) is</p> <blockquote> <p><b>ELEMENTARY</b> = <b>TIME</b>(2<sup><i>n</i></sup>) &cup; <b>TIME</b>(2<sup>2<sup><i>n</i></sup></sup>) &cup; <b>TIME</b>(2<sup>2<sup>2<sup><i>n</i></sup></sup></sup>) &cup; <b>TIME</b>(2<sup>2<sup>2<sup>2<sup><i>n</i></sup></sup></sup></sup>) &cup; ⋯</p> </blockquote> <p>If <i>L</i> were <b>ELEMENTARY</b>-complete, then it would belong to some level of this hierarchy, and all problems above could be reduced to it. But this hierarchy is known to be proper (time hierarchy theorem), contradiction.</p> http://mathoverflow.net/questions/7330/which-math-paper-maximizes-the-ratio-importance-length/25530#25530 Answer by Antonio E. Porreca for Which math paper maximizes the ratio (importance)/(length)? Antonio E. Porreca 2010-05-21T21:21:35Z 2010-05-21T21:21:35Z <p>Two fundamental papers in computational complexity theory and the theory of formal languages are very short:</p> <ul> <li><p>Neil Immerman, Nondeterministic space is closed under complementation, <em>SIAM Journal on Computing</em> 17(5), 935–938, 1988 (four pages);</p></li> <li><p>Róbert Szelepcsényi, The method of forcing for nondeterministic automata, <em>Bulletin of the EATCS</em> 33, 96–100, 1987 (five pages).</p></li> </ul> <p>Both papers independently prove what is now called the <a href="http://en.wikipedia.org/wiki/Immerman%E2%80%93Szelepcs%C3%A9nyi_theorem" rel="nofollow">Immerman-Szelepcsényi theorem</a>, i.e., that <a href="http://en.wikipedia.org/wiki/NSPACE" rel="nofollow">nondeterministic space complexity classes</a> are closed under complement, and in particular that context-sensitive languages are closed under complement. The authors shared the <a href="http://en.wikipedia.org/wiki/G%C3%B6del_Prize" rel="nofollow">Gödel Prize</a> in 1995 for their result.</p> <p>I’ve never read Szelepcsényi’s version, but <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.54.5941&amp;rep=rep1&amp;type=pdf" rel="nofollow">Immerman’s</a> is so short and sweet that I found it hard to believe at first that it actually works as a proof of such an important theorem.</p> http://mathoverflow.net/questions/24659/resources-for-learning-domain-theory/24714#24714 Answer by Antonio E. Porreca for Resources for learning domain theory? Antonio E. Porreca 2010-05-15T08:57:57Z 2010-05-15T08:57:57Z <p>I used the book <em>The Formal Semantics of Programming Languages</em> by G. Winskel for an undergraduate course, and I found it a reasonably good introduction to the topic; it also covers operational semantics and its relationship with denotational semantics, which I found quite enlightening since the former one is probably easier to grasp initially.</p> http://mathoverflow.net/questions/24083/reversible-turing-machines/24087#24087 Answer by Antonio E. Porreca for reversible Turing machines Antonio E. Porreca 2010-05-10T12:04:22Z 2010-05-10T12:04:22Z <p>I think your map <i>K<sub>S</sub></i> also needs to take the position of the tape head as input, or am I missing something?</p> <p>The classic paper <a href="http://www.dna.caltech.edu/courses/cs191/paperscs191/bennett1973.pdf" rel="nofollow">Logical reversibility of computation</a> by C.H. Bennett defines reversible Turing machines as</p> <blockquote> <p>a finite set of n-tape quadruples, no two of which overlap either in domain or range</p> </blockquote> <p>which should imply your notion of reversibility, assuming you allow an arbitrary alphabet instead of just &Sigma; = {0, 1}.</p> http://mathoverflow.net/questions/23032/what-is-the-intuitive-meaning-of-star-and-box-in-a-pure-type-system/23045#23045 Answer by Antonio E. Porreca for What is the intuitive meaning of star and box in a pure type system? Antonio E. Porreca 2010-04-29T21:49:48Z 2010-04-29T21:49:48Z <p>I seem to recall there’s a really good explanation of kinds and sorts in Sørensen and Urzyczyn’s <a href="http://www.amazon.com/Lectures-Curry-Howard-Isomorphism-Foundations-Mathematics/dp/0444520775/" rel="nofollow">Lectures on the Curry-Howard Isomorphism</a> (a previous version is available <a href="http://folli.loria.fr/cds/1999/library/pdf/curry-howard.pdf" rel="nofollow">online</a>).</p> http://mathoverflow.net/questions/21686/proofs-of-if-and-only-if-statements/21696#21696 Answer by Antonio E. Porreca for Proofs of if and only if statements Antonio E. Porreca 2010-04-17T22:01:24Z 2010-04-26T09:29:46Z <p>I think that, in most proofs of equivalence between models of computation (“a function can be computed by an automaton of type <em>A</em> iff it can be computed by an automaton of type <em>B</em>”), both directions usually offer some insight.</p> <p>This is a simple but fundamental example from complexity theory. Define <strong>NP</strong> to be the class of languages (equivalently, decision problems) recognised by nondeterministic Turing machines operating in polynomial time. Then:</p> <p><strong>Theorem.</strong> A language <em>L</em> is in <strong>NP</strong> iff there exist a <em>deterministic</em> Turing machine <em>M</em> operating in polynomial time and a polynomial <em>p</em> such that, for each string <em>x</em>,</p> <ul> <li><p>if <em>x</em> &isin; <em>L</em> then there exists a string <em>y</em> with |<em>y</em>| &le; <em>p</em>(|<em>x</em>|) such that <em>M</em> accepts (<i>x</i>, <i>y</i>);</p></li> <li><p>if <em>x</em> &notin; <em>L</em> then <em>M</em> rejects (<i>x</i>, <i>y</i>) for all strings <em>y</em> with |<em>y</em>| &le; <em>p</em>(|<em>x</em>|).</p></li> </ul> <p>The deterministic Turing machine <em>M</em> can be called a <em>verifier</em>, and the strings <em>y</em> accompanying each string <em>x</em> &isin; <em>L</em> that make <em>M</em> accept are called <em>short certificates</em>: they constitute an easily verifiable proof of membership of <em>x</em> in the language; no string outside <em>L</em> possesses such a membership proof.</p> <p>For a proof of this theorem see, for instance, <a href="http://en.wikipedia.org/wiki/NP_%28complexity%29#Equivalence_of_definitions" rel="nofollow">this page</a> on Wikipedia; notice that both implications have an easy but not completely trivial proof.</p> <p>The proof of “<em>L</em> has short certificates &rArr; <em>L</em> &isin; <strong>NP</strong>” shows how the “magic” of nondeterminism can be used to <em>guess</em> a certificate (if it exists for a particular input string).</p> <p>The proof of “<em>L</em> &isin; <strong>NP</strong> &rArr; <em>L</em> has short certificates”, on the other hand, shows that nondeterminism, which might appear an unrealistic notion, implies the very concrete existence of short, easily checkable proofs for some properties of the input that might be too hard to decide efficiently.</p> http://mathoverflow.net/questions/22189/what-is-your-favorite-strange-function/22218#22218 Answer by Antonio E. Porreca for What is your favorite "strange" function? Antonio E. Porreca 2010-04-22T16:37:49Z 2010-04-22T16:37:49Z <p><strong>The Busy Beaver function</strong></p> <p>Let &Sigma; be a finite alphabet, for instance {0, 1}; let <b>M</b> be the set of Turing machines with alphabet &Sigma;, and let <b>H</b> &sube; <b>M</b> be the set of Turing machines that halt when given the empty string &epsilon; as input.</p> <p>For each <i>M</i> &isin; <b>H</b>, Let <i>s</i>(<i>M</i>) be the number of steps performed by <i>M</i> before halting (when given &epsilon; as input).</p> <p>Finally, let <i>S</i> : &#8469; &rarr; &#8469; be the function defined by</p> <blockquote> <p><i>S</i>(<i>n</i>) = max {<i>s</i>(<i>M</i>) : <i>M</i> &isin; <b>H</b> and <i>M</i> has <i>n</i> states}</p> </blockquote> <p>Notice that <i>S</i> is well-defined, since only finitely many Turing machines with <i>n</i> states exist.</p> <p>In other words, <i>S</i>(<i>n</i>) is the maximum number of steps performed on &epsilon; among all halting Turing machines with <i>n</i> states. <i>S</i> is called the <a href="http://en.wikipedia.org/wiki/Busy_beaver" rel="nofollow">Busy Beaver function</a>.</p> <p>It turns out that <i>S</i> is uncomputable because it grows faster than any computable function, that is, for all recursive functions <i>f</i> : &#8469; &rarr; &#8469; we have <i>S</i>(<i>n</i>) > <i>f</i>(<i>n</i>) for large enough <i>n</i>, and in particular <i>f</i> is <i>o</i>(<i>S</i>).</p> http://mathoverflow.net/questions/21616/provability-of-termination-whats-wrong-with-my-reasoning/21626#21626 Answer by Antonio E. Porreca for Provability of termination. Whats wrong with my reasoning? Antonio E. Porreca 2010-04-16T22:34:58Z 2010-04-16T22:46:28Z <p>It is true that $H(A)$ implies that we have a proof of $H(A)$, and we can find it by enumeration: as you noted, a proof of $H(A)$ is just a finite sequence of configurations or states of program $i$ on input $x$, each one of them reachable from the previous one according to the rules described by program $i$ itself (hence, such a proof is algorithmically verifiable).</p> <p>The problem with your argument is that $\neg H(A)$ does <em>not</em> necessarily imply that we have a proof of it, as you assume when saying “But now we have a proof of $\neg H(A)$”. <em>Some</em> programs can indeed have a non-termination proof; for instance, a finite sequence of configurations of the program that repeat cyclically. But other programs can go through an infinite number of non-recurring configurations: thus, the notion of non-termination proof as a finite sequence of configurations is flawed.</p> <p>Even by giving a lot of thought to the question, you won’t probably find any satisfying notion of “non-termination proof” applicable to all programs. The reason is that such a notion is provably nonexistent (formally, the set of non-halting programs is not recursively enumerable).</p> http://mathoverflow.net/questions/21458/typesetting-mathematics-how-do-em-you-convert-text-into-pdf/21466#21466 Answer by Antonio E. Porreca for Typesetting mathematics: how do {\em you} convert text into pdf? Antonio E. Porreca 2010-04-15T15:12:27Z 2010-04-15T18:22:07Z <p>You can do margin kerning (aka “protrusion”) and font expansion in pdfLaTeX simply by loading the package <code>microtype</code> (i.e., by adding</p> <blockquote> <p><code>\usepackage{microtype}</code></p> </blockquote> <p>to the preamble). I also suggest using the <code>tracking</code> option for small-caps, which increases the space between letters (which is typographically correct, but <em>only</em> for small-caps and all-caps text):</p> <blockquote> <p><code>\usepackage[tracking=smallcaps]{microtype}</code></p> </blockquote> <p>For further information (and for several fine-tuning options) you can consult the <code>microtype</code> <a href="http://tug.ctan.org/tex-archive/macros/latex/contrib/microtype/" rel="nofollow">manual</a>.</p> <p>Edit: Yes, in my opinion and (I think) in a typographer’s opinion, these features do make a lot of difference. Margin kerning and font expansion help pdfLaTeX typeset the text, producing a lot less over/underfull hboxes. Letterspaced small-caps are also more legible and much more aesthetically pleasing.</p> http://mathoverflow.net/questions/21087/is-there-a-primitive-recursively-enumerable-set-whose-complement-is-not-such/21102#21102 Answer by Antonio E. Porreca for Is there a "primitive-recursively enumerable" set whose complement is not such? Antonio E. Porreca 2010-04-12T12:26:07Z 2010-04-12T12:59:17Z <p>This is an interesting question. From B. Rosser, <a href="http://www.jstor.org/sici?sici=0022-4812%28193609%291%3A3%3C87%3AEOSTOG%3E2%2E0%2ECO%3B2-7" rel="nofollow">Extensions of some theorems of Gödel and Church</a>:</p> <blockquote> <p>Corollary I. <em>If a class can be enumerated (allowing repetitions) by a general recursive function, it can be enumerated (allowing repetitions) by a primitive recursive function.</em></p> </blockquote> <p>Hence any complete recursively enumerable set (such as <em>K</em>) should work.</p> http://mathoverflow.net/questions/38460/arithmetic-of-ordered-sets-more-general-than-ordinals/38526#38526 Comment by Antonio E. Porreca Antonio E. Porreca 2010-09-14T10:37:43Z 2010-09-14T10:37:43Z Does non-well-founded set theory provide a more appropriate setting for non-well-founded orders, e.g., for finding canonical representatives of each order type? I’m not familiar with the subject. http://mathoverflow.net/questions/38460/arithmetic-of-ordered-sets-more-general-than-ordinals/38519#38519 Comment by Antonio E. Porreca Antonio E. Porreca 2010-09-14T10:18:44Z 2010-09-14T10:18:44Z Thanks, I’ll take a look at it. http://mathoverflow.net/questions/38460/arithmetic-of-ordered-sets-more-general-than-ordinals Comment by Antonio E. Porreca Antonio E. Porreca 2010-09-14T10:18:10Z 2010-09-14T10:18:10Z Joel, me and one of my colleagues were just toying with that idea; we’re not sure about the interpretation either (except maybe for a “universe without a beginning” where time has the same order type as ℤ). http://mathoverflow.net/questions/35461/interesting-complexity-classes-pr-subsetneq-c-subsetneq-r/35495#35495 Comment by Antonio E. Porreca Antonio E. Porreca 2010-08-13T14:08:40Z 2010-08-13T14:08:40Z Sorry, I answered before your edit to the original question; now I see you already excluded the “PR + Ackermann” case. :-) http://mathoverflow.net/questions/35461/interesting-complexity-classes-pr-subsetneq-c-subsetneq-r Comment by Antonio E. Porreca Antonio E. Porreca 2010-08-13T13:35:56Z 2010-08-13T13:35:56Z Could you please edit the original question according to your last comment? http://mathoverflow.net/questions/35461/interesting-complexity-classes-pr-subsetneq-c-subsetneq-r Comment by Antonio E. Porreca Antonio E. Porreca 2010-08-13T10:59:18Z 2010-08-13T10:59:18Z Maybe I misunderstood something, but you seem to claim that membership in PR is decidable. It is not (see Rice’s theorem). I’m not sure, but it might be possible if your programs are written in some non-Turing-equivalent programming language. Could you clarify? http://mathoverflow.net/questions/35401/post-correspondence-problem/35407#35407 Comment by Antonio E. Porreca Antonio E. Porreca 2010-08-13T00:48:18Z 2010-08-13T00:48:18Z I guess the point of confusion here is that, even when you’ve fixed a group <i>G</i>, you still have another input to give to the hypothetical algorithm (the “word” to check), and the same reasoning applies: you cannot find a specific “undecidable word”. A specific group having undecidable word problem and a specific “undecidable PCP instance” are two very different objects. http://mathoverflow.net/questions/35401/post-correspondence-problem/35403#35403 Comment by Antonio E. Porreca Antonio E. Porreca 2010-08-13T00:42:32Z 2010-08-13T00:42:32Z I’m not sure I’ve ever met this argument before, thanks! http://mathoverflow.net/questions/35401/post-correspondence-problem Comment by Antonio E. Porreca Antonio E. Porreca 2010-08-12T23:14:58Z 2010-08-12T23:14:58Z By the way, it seems to me that the “computability-theory” tag is more appropriate than “cs.cc.complexity-theory”, as we aren’t dealing with complexity matters here. http://mathoverflow.net/questions/34099/the-best-text-to-study-both-incompleteness-theorems/34102#34102 Comment by Antonio E. Porreca Antonio E. Porreca 2010-08-01T12:11:17Z 2010-08-01T12:11:17Z No, Franz&#233;n doesn’t give full proofs; it might be interesting, however, for some philosophical discussion (which, I think, is missing in Smith’s handouts). http://mathoverflow.net/questions/32666/when-is-something-too-big-to-be-a-set/32674#32674 Comment by Antonio E. Porreca Antonio E. Porreca 2010-07-20T20:08:51Z 2010-07-20T20:08:51Z I like your last sentence very much. http://mathoverflow.net/questions/32320/what-is-the-relationship-between-translation-and-time-complexity/32336#32336 Comment by Antonio E. Porreca Antonio E. Porreca 2010-07-19T16:06:04Z 2010-07-19T16:06:04Z Probably the question becomes less interesting this way, but I’d go as far as to say that the encoding is itself <i>part of the statement of the problem</i> (particularly when we describe decision problems as languages). http://mathoverflow.net/questions/31893/what-is-the-history-of-the-y-combinator Comment by Antonio E. Porreca Antonio E. Porreca 2010-07-14T19:56:53Z 2010-07-14T19:56:53Z Dan, according to the paper by Cardone and Hindley I posted in my answer, that doesn’t seem to be the case. http://mathoverflow.net/questions/31577/decision-problem-restricted-to-inputs-that-satisfy-some-necessary-condition Comment by Antonio E. Porreca Antonio E. Porreca 2010-07-12T19:09:36Z 2010-07-12T19:09:36Z Emil, can NC be determined in <i>nondeterministic</i> polytime? If so (as in the NC = 3-colourability example) then it seems to me that Problem 2 does belongs to NP: just ignore the “promise” or any NC certificate given as input, and recheck the property before testing 3-colourability. On the other hand, if NC is too hard (e.g., NEXPTIME-complete) you have to “trust” the promise, because you don’t have the time to verify it (and the problem is not in NP). http://mathoverflow.net/questions/31448/lower-bounds-in-theoretical-computer-science/31449#31449 Comment by Antonio E. Porreca Antonio E. Porreca 2010-07-11T21:27:49Z 2010-07-11T21:27:49Z I’ve always found this result fascinating: less than log log n tape is no better than no tape at all.