User frank - MathOverflow

Smallest base to reach partial recursive functions as a closure of unbound search

2013-05-06T12:08:44Z

It is customary to define the class of partial recursive functions by taking the set of primitive recursive functions $PR$ and taking closure over unbound search operation.

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.

For example Grzegorczyk proves that

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$.

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 Grzegorczyk-hierarchy. I don't, however, see how to change the "unique $x$ such.." to "smallest $x$ such..".

Grzegorczyk-hierarchy, growth-rate and functions with finite image

2013-03-25T06:54:31Z

Grzegorczyk-hierarchy 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.

How would one define a finite image function for every $i$ that is in $\mathcal{E}_i$ but not in the lower levels?

Should one attack hard problems?

2013-02-27T07:27:33Z

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.

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?

Math for a cake

2012-12-29T09:55:13Z

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.

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".

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.)

Any ideas what we could put on top of the cake?

How to tell a paradox from a "paradox"?

2012-09-26T07:45:34Z

Russell's paradox showed that naive set theory leads to a contradiction. This was something that was taken seriously and caused a lot of work.

Now, Banach–Tarski paradox 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.

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.

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?

Who introduced the concept of Primitive recursive functions?

2012-07-05T11:00:27Z

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.

Ackermann published the famous Ackermann function in his paper "Zum Hilbertschen Aufbau der reellen Zahlen" 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.

Who introduced primitive recursive functions first?

Answer by Frank for Examples of interesting false proofs

2012-05-20T07:25:23Z

Claim: All positive integers are equal.

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

If $n=1$, we clearly have $a=b=1$.

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.

Is there a fair coin?

2011-11-01T12:35:14Z

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.

Is there such a proof?

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.

The hardness of computing inverse

2011-06-21T07:03:46Z

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.

Are there functions $f$ that are computable in polynomial time but whose inverse is known not to be computable in polynomial time?

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?

Prenex normal form vs. quantifier rank

2011-05-03T10:08:07Z

Consider first-order logic with some fixed, relational vocabulary $\tau$. A sentence is a formula in this logic with no free variables.

A sentence is in prenex normal form, 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.

Let quantifier rank of a sentence be the maximum number of nested quantifications in it.

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).

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$.

How would one transform a formula to prenex normal form in a way that would keep the quantifier rank untouched?

Answer by Frank for Your favorite surprising connections in Mathematics

2011-03-13T16:39:31Z

I'll take a risk and provide a slightly off-topic connection (feel free to downvote).

How come mathematics can describe physical phenomenons so accurately.

I faced this in the article by Eugene Wigner "The Unreasonable Effectiveness of Mathematics in the Natural Sciences".

$2$-variable segment of FO over ordered, finite structures

2011-04-20T12:51:10Z

Let $FO$ be first-order logic and $FO^k$ be $k$-variable segment of $FO$, i.e. $FO^k$ has only $k$ variables.

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$.

Is this true? Are there any assumptions about the vocabulary?

Suggestions for mathematics encyclopedia

2011-04-07T07:14:22Z

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.

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).

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.

Any suggestions?

Answer by Frank for Computer Science for Mathematicians

2011-03-14T15:59:02Z

To the latter I suggest "Computable functions" By Nikolai Konstantinovich Vereshchagin and Alexander Shen. It covers the basic stuff about computability and is approachable to a mathematician.

Syntactically capturing complexity classes

2011-02-14T15:01:45Z

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$.

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.

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).

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.

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?

Is this even possible?

Between mu- and primitive recursion

2010-11-17T13:39:19Z

It is well known that primitive recursion is not powerful enough to express all functions, Ackermann function being probably the best known example.

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.

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.

This suggests there is at least one level between mu-recursion and primitive recursion.

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.

Answer by Frank for Examples of common false beliefs in mathematics.

2011-02-06T20:02:57Z

I've seen in many introductory texts to matrices/linear algebra the claim "scalars are (just) $1$-by-$1$ matrices".

If this were true we could scalar-multiply only $1$-by-$n$ matrices...

Enumerating levels of Grzegorczyk-hierarchy

2011-01-20T12:04:55Z

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.

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}$?

Comment by Frank

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!

Comment by Frank

2013-05-07T11:08:31Z

@Emil Hah, thanks. I was sloppy there.

Comment by Frank

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.

Comment by Frank

2013-05-06T12:38:26Z

What are these two $\Delta_0$ functions that we can go with?

Comment by Frank

2013-04-24T07:58:32Z

Are you perhaps looking for something similar to partition regularity? en.wikipedia.org/wiki/Partition_regularity

Comment by Frank

2013-04-04T06:55:09Z

Personally I don't find asking inappropriate, but I guess this is something where opinions vary.

Comment by Frank

2013-04-02T09:35:54Z

Have you emailed the author about the first question?

Comment by Frank

2013-03-26T13:18:05Z

This looks very promising, I will go through the details before marking this an answer. Thank you.

Comment by Frank

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 mathoverflow.net/questions/33033/… or mathoverflow.net/questions/14607/…

Comment by Frank

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.

Comment by Frank

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.

Comment by Frank

2012-12-31T13:11:00Z

I thought of this but the problem is I just can't decide which one is a theorem.

Comment by Frank

2012-10-09T06:38:25Z

It would be nice if You wrote the list with few comments here instead of placing a link.

Comment by Frank

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...

Comment by Frank

2011-11-01T18:15:27Z

Ah, there is the catch "...inhomogeneity doesn’t matter for flipped coins" -- they limit it to coins. I thought it was about any "coin like" flat object and with some thinking I concluded that there is no "fair buttered bread" due to Murphy's law... Thank you for the reference!