User frank - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-26T01:19:44Z http://mathoverflow.net/feeds/user/10891 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/129823/smallest-base-to-reach-partial-recursive-functions-as-a-closure-of-unbound-search Smallest base to reach partial recursive functions as a closure of unbound search Frank 2013-05-06T12:08:44Z 2013-05-06T15:03:48Z <p>It is customary to define the class of <a href="http://en.wikipedia.org/wiki/Mu-recursive_function" rel="nofollow">partial recursive functions</a> by taking the set of <a href="https://en.wikipedia.org/wiki/Primitive_recursive" rel="nofollow">primitive recursive functions</a> $PR$ and taking closure over unbound search operation.</p> <p>Do we need the "whole" set of primitive recursive functions as a base to reach the class of partial recursive functions with the closure? It seems reasonable to assume that unbound search could be used in the place of primitive recursion to reach the class $PR$ from a smaller base class. </p> <p>For example Grzegorczyk proves that </p> <blockquote> <blockquote> <p>Every computable function can be presented in the form $f(u)=A(ix[B(u,x)=0])$, where $A$ and $B$ are functions of the class $\mathcal{E}_0$.</p> </blockquote> </blockquote> <p>Here $ix[B(u,x)=0]$ is the unique $x$ such that $B(u,x)=0$ and $\mathcal{E}_0$ is the lowest set in <a href="http://en.wikipedia.org/wiki/Grzegorczyk_hierarchy" rel="nofollow">Grzegorczyk-hierarchy</a>. I don't, however, see how to change the "unique $x$ such.." to "smallest $x$ such..". </p> http://mathoverflow.net/questions/125512/grzegorczyk-hierarchy-growth-rate-and-functions-with-finite-image Grzegorczyk-hierarchy, growth-rate and functions with finite image Frank 2013-03-25T06:54:31Z 2013-03-25T14:35:09Z <p><a href="http://en.wikipedia.org/wiki/Grzegorczyk_hierarchy" rel="nofollow">Grzegorczyk-hierarchy</a> divides primitive recursive functions in distinct classes with respect to their growth-rate. It seems that the higher we go the hierarchy, the more tools we have to define functions with finite image that can't be defined in the lower levels of the hierarchy. I have been trying to define functions with finite image that exist only in "high enough" in the hierarchy, but so far I haven't succeeded. </p> <p>How would one define a finite image function for every $i$ that is in $\mathcal{E}_i$ but not in the lower levels?</p> http://mathoverflow.net/questions/123081/should-one-attack-hard-problems Should one attack hard problems? Frank 2013-02-27T07:27:33Z 2013-03-11T08:44:00Z <p>When I applied for a PhD student position I had an interview with two professors. Somehow we touched the problem if $P$ is $NP$ and, once we got there, for some reason both professors made it clear that in their opinion there is absolutely no point attacking such a hard problem. Of course this is the case for a starting student, it is more fruitful to build the basis first. But they basically stated that the problem has been studied by so smart researchers that no mortal could do better anyway.</p> <p>This makes me wonder should one attack such hard problems at all? If one should, why and when? Will studying hard problems span new ideas? Is it even a necessity to understand some hard problems and, especially, why they are hard to solve? Or is it just pure waste of time? Or is it that one should learn some hard problems to educate oneself but not spend time attacking them?</p> http://mathoverflow.net/questions/117494/math-for-a-cake Math for a cake Frank 2012-12-29T09:55:13Z 2012-12-29T22:15:47Z <p>My wife likes to decorate birthday cakes. She told me that she will make a math cake for my birthday and I should provide her a "famous math formula" to be written on the top of the cake.</p> <p>I realized I can name dozens of physics related famous formulas that one could recognize (Maxwell's equations, Newtons laws, Einstein's $E=mc^2$...) but I couldn't name one that would be more "math related". </p> <p>Writing some axioms wouldn't work, they take too much space. The famous theorems I know of are not really "a formula" but more like of "statements" that would need some background, or they are not visually appealing (like Fermat's last theorem). (Quests are not math-oriented thus the visual side matters.)</p> <p>Any ideas what we could put on top of the cake?</p> http://mathoverflow.net/questions/108138/how-to-tell-a-paradox-from-a-paradox How to tell a paradox from a "paradox"? Frank 2012-09-26T07:45:34Z 2012-09-26T17:39:14Z <p><a href="http://en.wikipedia.org/wiki/Russell%2527s_paradox" rel="nofollow">Russell's paradox</a> showed that naive set theory leads to a contradiction. This was something that was taken seriously and caused a lot of work.</p> <p>Now, <a href="http://en.wikipedia.org/wiki/Banach-Tarski_paradox" rel="nofollow">Banach–Tarski paradox</a> is arises from a result that a ball can be decomposed into finite amount of pieces and the pieces can be used to built two identical copies of the decomposed ball. Banach-Tarski paradox is often treated as a "paradox", basicly meaning that, yes, it is counter intuitive but yet there is no problem - mathematics just occasionally is counter intuitive.</p> <p>To be honest, I have never understood why Banach-Tarski is not a "real" paradox but not being expert of measure theory I chose to accept the common view.</p> <p>Is there some high level explanation on how to tell a paradox from a "paradox"? What is it that makes a counter intuitive result to a "real mathematical paradox" that we should start worrying about?</p> http://mathoverflow.net/questions/101393/who-introduced-the-concept-of-primitive-recursive-functions Who introduced the concept of Primitive recursive functions? Frank 2012-07-05T11:00:27Z 2012-07-05T13:02:05Z <p>I have thought that Gödel introduced the concept of Primitive recursive functions in his seminal paper "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme" (I hope I got the title right...). This paper, to best of my knowledge, was published in 1931.</p> <p>Ackermann published the famous Ackermann function in his paper <a href="http://eretrandre.org/rb/files/Ackermann1928_126.pdf" rel="nofollow">"Zum Hilbertschen Aufbau der reellen Zahlen"</a> in (again, to best of my knowledge) 1928. His publication seems to enclose primitive recursive functions and the main results is that there exists a total computable function outside PR. This suggests that PR has been known prior 1928, thus prior Gödel's work.</p> <p>Who introduced primitive recursive functions first?</p> http://mathoverflow.net/questions/94742/examples-of-interesting-false-proofs/97467#97467 Answer by Frank for Examples of interesting false proofs Frank 2012-05-20T07:25:23Z 2012-05-20T07:25:23Z <p>Claim: All positive integers are equal.</p> <p>Proof. Let $a$ and $b$ be positive integers. Let $n = M(a,b)$, where $M$ denotes the larger of $a$ and $b$. By induction on $n$ we get</p> <p>If $n=1$, we clearly have $a=b=1$.</p> <p>General case: Suppose $n=k$ implies $a=b$. Let now $n=k+1$. We have $M(a,b)=k+1$ thus $M(a-1,b-1)=k$, and from induction hypothesis $a-1=b-1$, so $a=b$ and the claim follows.</p> http://mathoverflow.net/questions/79704/is-there-a-fair-coin Is there a fair coin? Frank 2011-11-01T12:35:14Z 2011-11-01T14:13:26Z <p>I attended a course on stochastic processes a few years ago. During the course the lecturer mentioned that there is a mathematical proof (with some assumptions, naturally) of non-existence of a fair coin. Now I can't recall the details and can't locate the paper.</p> <p>Is there such a proof?</p> <p>I vaguely remember that the idea was to prove that given that coin's sides are distinguishable (by the structure, not color) one can't make the coin fully balanced.</p> http://mathoverflow.net/questions/68348/the-hardness-of-computing-inverse The hardness of computing inverse Frank 2011-06-21T07:03:46Z 2011-06-21T10:43:06Z <p>Say we have a one-to-one (total) function $f:\mathbb{N}\to\mathbb{N}$ and a Turing-machine $T_f$ that computes it. Suppose further that $T_f$ runs in polynomial time wrt. length of the input.</p> <blockquote> <p>Are there functions $f$ that are computable in polynomial time but whose inverse is known not to be computable in polynomial time?</p> </blockquote> <p>Does the situation change if we drop the one-to-one requirement and define the inverse as, say, min$(f^{-1})$? How about if we change the complexity class in question?</p> http://mathoverflow.net/questions/63788/prenex-normal-form-vs-quantifier-rank Prenex normal form vs. quantifier rank Frank 2011-05-03T10:08:07Z 2011-05-03T17:14:04Z <p>Consider first-order logic with some fixed, relational vocabulary $\tau$. A sentence is a formula in this logic with no free variables.</p> <p>A sentence is in <a href="http://en.wikipedia.org/wiki/Prenex_normal_form" rel="nofollow">prenex normal form</a>, if all quantifiers are moved to the front. For example $\exists x\exists y(P(x)\to P(y))$ is in prenex normal form whereas $\exists x( P(x)\lor \exists y(P(x)\to P(y)))$ is not.</p> <p>Let quantifier rank of a sentence be the maximum number of nested quantifications in it.</p> <p>Now, we know that quantifier rank is a measure of complexity of a first-order formula in the sense that there are only a finite number of sentences of a fixed quantifier rank up to logical equivalence (lets consider only finite models). </p> <p>If we have a sentence of the form $\varphi \equiv \exists x(\exists y \alpha(x,y)\lor\exists y \beta(x,y))$, where $\alpha$ and $\beta$ are formulas with two free variables $x$ and $y$, it is straightforward to transform it to a prenex form by simply renaming the occurences of $y$s and shifting quantifiers in front, i.e. $\exists x\exists y_1\exists y_2(\alpha(x,y_1)\lor \beta(x,y_2))$. But now the originating formula had quantifier rank of $2$ when the prenex form formula has quantifier rank $3$.</p> <p>How would one transform a formula to prenex normal form in a way that would keep the quantifier rank untouched? </p> http://mathoverflow.net/questions/14574/your-favorite-surprising-connections-in-mathematics/58342#58342 Answer by Frank for Your favorite surprising connections in Mathematics Frank 2011-03-13T16:39:31Z 2011-04-22T22:19:08Z <p>I'll take a risk and provide a slightly off-topic connection (feel free to downvote).</p> <blockquote> <p>How come mathematics can describe physical phenomenons so accurately.</p> </blockquote> <p>I faced this in the article by <a href="http://en.wikipedia.org/wiki/The_Unreasonable_Effectiveness_of_Mathematics_in_the_Natural_Sciences" rel="nofollow">Eugene Wigner "The Unreasonable Effectiveness of Mathematics in the Natural Sciences"</a>. </p> http://mathoverflow.net/questions/62404/2-variable-segment-of-fo-over-ordered-finite-structures $2$-variable segment of FO over ordered, finite structures Frank 2011-04-20T12:51:10Z 2011-04-20T22:01:49Z <p>Let $FO$ be first-order logic and $FO^k$ be $k$-variable segment of $FO$, i.e. $FO^k$ has only $k$ variables.</p> <p>To my understanding, for every sentence $\varphi\in FO$ there exists a sentence $\psi\in FO^2$ such that for all finite structures $\mathfrak{A}$ with linear order it is the case that $\mathfrak{A}\vDash\varphi$ iff $\mathfrak{A}\vDash\psi$.</p> <p>Is this true? Are there any assumptions about the vocabulary? </p> http://mathoverflow.net/questions/60895/suggestions-for-mathematics-encyclopedia Suggestions for mathematics encyclopedia Frank 2011-04-07T07:14:22Z 2011-04-13T18:16:41Z <p>On daily basis I need to check (and re-check and re-check...) some definitions and main theorems that are not in my research area. Usually I accomplish this by a Google-search and/or a visit to our library. Unfortunately this doesn't work too well as the local library is a small one and internet seems to be a contradictive entity on its own. </p> <p>Are there any must-to-have mathematical encyclopedia that one should invest to when starting to work in a math-oriented research field? I'm mainly interested in discrete mathematics and logic, but it definitely wouldn't hurt to have a wider scope in the book (say, for example, optimization, calculus and some probability theory). </p> <p>I'm not interested in any study material, but a (probably very heavy) book with short listing / explanation of the basic definitions and the useful theories from different areas. </p> <p>Any suggestions?</p> http://mathoverflow.net/questions/51217/computer-science-for-mathematicians/58439#58439 Answer by Frank for Computer Science for Mathematicians Frank 2011-03-14T15:59:02Z 2011-03-14T15:59:02Z <p>To the latter I suggest <a href="http://books.google.com/books?id=A6uvsks0abgC&amp;printsec=frontcover&amp;dq=%2522computable+functions%2522&amp;source=bl&amp;ots=88WIabGWRw&amp;sig=afAhJNb3qrO9ALlrHo4qvtvWGbU&amp;hl=en&amp;ei=bDp-TaukL8b5sgb9v_XbBw&amp;sa=X&amp;oi=book_result&amp;ct=result&amp;resnum=6&amp;ved=0CEAQ6AEwBQ#v=onepage&amp;q&amp;f=false" rel="nofollow">"Computable functions" By Nikolai Konstantinovich Vereshchagin and Alexander Shen</a>. It covers the basic stuff about computability and is approachable to a mathematician.</p> http://mathoverflow.net/questions/55415/syntactically-capturing-complexity-classes Syntactically capturing complexity classes Frank 2011-02-14T15:01:45Z 2011-03-03T11:07:22Z <p>Primitive recursive functions are syntactically constructible in the sense that from a set of "axioms" we can build every function in the set $PR$. This basicly means that we can build a machine that prints the definition for every function in $PR$.</p> <p>Now, we can build hierarchies in the set $PR$ by adding some semantic restrictions. For example Grzegorczyk created hierarchy $\{\mathcal{E}_i\}$ by restricting the rate of growth of the functions in each level.</p> <p>I found papers mentioning the fact that if we take the second level of Grzegorczyk-hierarchy and define $E_2 = \{ f\in\mathcal{E}_2| ran(f)\in\{0,1\}\}$ (i.e. give yet another semantic restriction), then $E_2$ encapsulates LINSPACE (to my understanding its not actually this straightforward, but the idea should come clear).</p> <p>In this construction we started defining functions syntactically and added some semantic constraints to come up with a class of functions computable in linear space. </p> <p>This motivates to ask if there exists any constructions which provide ways to deploy purely syntactic machinery to produce, say, all the Turing-machines that run in polynomial space / time / whatever complexity class? Or functions instead of Turing-machines?</p> <p>Is this even possible?</p> http://mathoverflow.net/questions/46350/between-mu-and-primitive-recursion Between mu- and primitive recursion Frank 2010-11-17T13:39:19Z 2011-02-07T05:53:22Z <p>It is well known that primitive recursion is not powerful enough to express all functions, Ackermann function being probably the best known example.</p> <p>Now, in the logic courses (that I have had look at) one always proceeded from primitive recursion to mu-recursion. In computer science terms this basicly means we are jumping from a formalism where programs are quaranteed to halt to a Turing-complete formalism where halting is a non-computable property i.e. we can't say for every program if it will eventually halt.</p> <p>I got curious if there is any hierarchy between primitive recursion and mu-recursion. After a while I found a programming language called Charity. In Charity (according to Wikipedia) all programs are quaranteed to stop, thus its not Turing-complete, but, on the other hand, it is expressive enough to implement Ackermann function.</p> <p>This suggests there is at least one level between mu-recursion and primitive recursion. </p> <p>My question is: does there exists any other halt-for-sure formalisms that are more expressive than primitive recursion? Or, even better, does there exist some known hierarchies between mu-recursive and primitive recursive functions? I'm curious about how "much" we can compute with a formalism that guarantees halting.</p> http://mathoverflow.net/questions/23478/examples-of-common-false-beliefs-in-mathematics/54558#54558 Answer by Frank for Examples of common false beliefs in mathematics. Frank 2011-02-06T20:02:57Z 2011-02-06T20:02:57Z <p>I've seen in many introductory texts to matrices/linear algebra the claim "<em>scalars are (just) $1$-by-$1$ matrices</em>".</p> <p>If this were true we could scalar-multiply only $1$-by-$n$ matrices... </p> http://mathoverflow.net/questions/52606/enumerating-levels-of-grzegorczyk-hierarchy Enumerating levels of Grzegorczyk-hierarchy Frank 2011-01-20T12:04:55Z 2011-01-22T01:11:52Z <p>Grzegorczyk has divided the class of primitive recursive functions to Grzegorczyk-hierarchy by their rate of growth. In this hierarchy $E_i\subset E_{i+1}$ and the subset-relation is strict. Also $\cup_{i}E_i = Pr$, i.e. the union of all levels is equal to the class of primitive recursive functions.</p> <p>I know that primitive recursive functions are recursively enumerable, but I wonder if the levels of Grzegorczyk-hierarchy are recursively enumerable, i.e. is it possible to "scan through" some level $E_i$ or, even better, functions in $E_i\setminus E_{i-1}$?</p> http://mathoverflow.net/questions/129823/smallest-base-to-reach-partial-recursive-functions-as-a-closure-of-unbound-search/129835#129835 Comment by Frank Frank 2013-05-07T12:32:55Z 2013-05-07T12:32:55Z With your idea its seems fairly easy to prove that even $\mathcal{E}_0$ will do and this is what I was after to. Thank you! http://mathoverflow.net/questions/129823/smallest-base-to-reach-partial-recursive-functions-as-a-closure-of-unbound-search/129835#129835 Comment by Frank Frank 2013-05-07T11:08:31Z 2013-05-07T11:08:31Z @Emil Hah, thanks. I was sloppy there. http://mathoverflow.net/questions/129823/smallest-base-to-reach-partial-recursive-functions-as-a-closure-of-unbound-search/129827#129827 Comment by Frank Frank 2013-05-06T12:52:43Z 2013-05-06T12:52:43Z Thank you. I was not expecting an answer from this perspective so I need to think both the question and the answer a bit further. http://mathoverflow.net/questions/129823/smallest-base-to-reach-partial-recursive-functions-as-a-closure-of-unbound-search/129827#129827 Comment by Frank Frank 2013-05-06T12:38:26Z 2013-05-06T12:38:26Z What are these two $\Delta_0$ functions that we can go with? http://mathoverflow.net/questions/118830/a-general-framework-for-ramsey-theory Comment by Frank Frank 2013-04-24T07:58:32Z 2013-04-24T07:58:32Z Are you perhaps looking for something similar to partition regularity? <a href="https://en.wikipedia.org/wiki/Partition_regularity" rel="nofollow">en.wikipedia.org/wiki/Partition_regularity</a> http://mathoverflow.net/questions/125596/godel-on-recursion-theoretic-hierarchies Comment by Frank Frank 2013-04-04T06:55:09Z 2013-04-04T06:55:09Z Personally I don't find asking inappropriate, but I guess this is something where opinions vary. http://mathoverflow.net/questions/125596/godel-on-recursion-theoretic-hierarchies Comment by Frank Frank 2013-04-02T09:35:54Z 2013-04-02T09:35:54Z Have you emailed the author about the first question? http://mathoverflow.net/questions/125512/grzegorczyk-hierarchy-growth-rate-and-functions-with-finite-image/125532#125532 Comment by Frank Frank 2013-03-26T13:18:05Z 2013-03-26T13:18:05Z This looks very promising, I will go through the details before marking this an answer. Thank you. http://mathoverflow.net/questions/123081/should-one-attack-hard-problems Comment by Frank Frank 2013-02-27T13:52:56Z 2013-02-27T13:52:56Z @quid I'm disappointed this question got closed. I take advice requests are not welcome here. Funny that on the right side there are many questions of the same style that are not closed. For example <a href="http://mathoverflow.net/questions/33033/how-much-reading-do-you-do-before-you-attack-a-problem" rel="nofollow" title="how much reading do you do before you attack a problem">mathoverflow.net/questions/33033/&hellip;</a> or <a href="http://mathoverflow.net/questions/14607/when-to-start-reviewing" rel="nofollow" title="when to start reviewing">mathoverflow.net/questions/14607/&hellip;</a> http://mathoverflow.net/questions/123081/should-one-attack-hard-problems/123088#123088 Comment by Frank Frank 2013-02-27T11:04:15Z 2013-02-27T11:04:15Z Problem is that often failed attempts don't get published thus its hard to say what has been tried without success. http://mathoverflow.net/questions/112337/recursively-enumerable-sets-as-range-sets-of-functions-in-grzegorczyk-hierarchy Comment by Frank Frank 2013-02-19T12:35:02Z 2013-02-19T12:35:02Z In case you're interested, the last theorem in Grzegorczyk's paper Some classes of recursive functions, where the hierarchy is introduced, proves that $\mathcal{E}_0$ suffices, as is shown in the answer. http://mathoverflow.net/questions/117494/math-for-a-cake/117496#117496 Comment by Frank Frank 2012-12-31T13:11:00Z 2012-12-31T13:11:00Z I thought of this but the problem is I just can't decide which one is a theorem. http://mathoverflow.net/questions/10146/good-books-on-problem-solving-math-olympiad/109145#109145 Comment by Frank Frank 2012-10-09T06:38:25Z 2012-10-09T06:38:25Z It would be nice if You wrote the list with few comments here instead of placing a link. http://mathoverflow.net/questions/90002/reference-request-non-standard-models-of-pa Comment by Frank Frank 2012-03-02T10:16:47Z 2012-03-02T10:16:47Z Kaye's book is available in pdf-format and can be found from Google. I'm not sure if its appropriate to link it here, tough... http://mathoverflow.net/questions/79704/is-there-a-fair-coin/79707#79707 Comment by Frank Frank 2011-11-01T18:15:27Z 2011-11-01T18:15:27Z Ah, there is the catch &quot;...inhomogeneity doesn’t matter for flipped coins&quot; -- they limit it to coins. I thought it was about any &quot;coin like&quot; flat object and with some thinking I concluded that there is no &quot;fair buttered bread&quot; due to Murphy's law... Thank you for the reference!