MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I was curious as to whether given any problem, lets say:

$x^2-1 = 0$

There exists a function that given this set of symbols as input return the exact set of symbols contained in the answer. In this case $x=-1,x=1$

Surely, given that the process of getting from the problem's set of symbols to the solution's is not random, there exists a function that does what I said above.

The method I came up with involves mapping the symbols to numbers as follows:

$ x \to 1$

$ uppower \to 2$

$ downpower \to 3$

$ - \to 4$

$ = \to 5$

$ , \to 6$

Then for the numbers 0 - 9 $(n\to n+7)$. And that should do for now.

Then to start approximating the function we can express the problem (using Godel encoding) with a unique number. In this case:

$2^1*3^2*5^9*7^3*11^4*13^8 = x_1$

And we can express the solution as:

$2^1*3^5*5^4*7^8*11^6*13^1*17^5*19^8 = y_1$

So $a = y_1$ and our first approximation for our universal function is:

$a = y$

Now we can continue with a second data point and solve it with the previous simultaneously - e.g $(bx_1+a = y_1$ and $ bx_2+a = y_2)$. Keep adding points and solving in the same style (for the amount of points you have $p$ solve that many polynomials with the highest power as $p-1$). Eventually it should give an accurate answer given any quadratic to solve.

If true then you could keep adding points outside the scope of quadratics to any non-random progression from one sequence of symbols to another, until it became a universal function.

If false, then why? I know there are an infinite amount of functions for any given set of points, but surely given enough data within a particular range this method is likely to get pretty close to it, and if it doesn't then the process is probably random. Or maybe i am wrong in my assumption that there should be a function mapping a non-random symbolic problem to its solution. Or maybe something in my method limits it. Either or another way I would be most interested to know, thanks, Reuben.

P.S. I didn't know what to tag this in so any suggestions would be welcome!

share|cite|improve this question

closed as off topic by Chandan Singh Dalawat, Dan Petersen, Andreas Blass, Steven Landsburg, Mariano Suárez-Alvarez Mar 18 '13 at 15:18

Questions on MathOverflow are expected to relate to research level mathematics within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here.If this question can be reworded to fit the rules in the help center, please edit the question.

Maybe you should write x^2-1=0 in the second line. – Michael Bächtold Mar 18 '13 at 11:58
Michael: Why is the expression $x^2-1=0$ any more a "problem" than the expression $x^2-1$ ? – Steven Landsburg Mar 18 '13 at 14:24
up vote 5 down vote accepted

Your question seems to concern the issue of the computability of solutions of computable functions, and the larger context for such a question is the subject known as computable analysis.

Carl Mummert has a very nice blog post concerning the following theorems, which I believe lie at the heart of your question.

Here are several interesting results from computable analysis:

Theorem 1. If $f$ is a computable function from $\mathbb{R}$ to $\mathbb{R}$ and $a$ is an isolated root of $f$, then α is computable.

Corollary 2. If $p(x)$ is a polynomial over $\mathbb{R}$ with computable coefficients, then every root of $p(x)$ is computable.

Theorem 3. There is a effective closed subset of $\mathbb{R}$ which is nonempty (in fact, uncountable) but which has no computable point.

Theorem 4. There is a computable function from $\mathbb{R}$ to $\mathbb{R}$ which has uncountably many roots but no computable roots.

But your question inquires not for an algorithm for each function separately, but a uniform algorithm working with all equations to be solved. Here, there are various non-uniformity results that one can mention.

For example, by the MRDP theorem, there can be no computable algorithm that determines whether a given integer polynomial equation in several variables has a solution in the integers.

But meanwhile, there of course can be a computational procedure that maps any given Diophantine equation to an integer solution of it, when there is a solution, for one may simply undertake exhaustive search.

share|cite|improve this answer
Vote this comment up if I should delete this answer. – Joel David Hamkins Mar 18 '13 at 12:05
I was initially appalled to see that anyone had answered this question, but I learned so much from the answer that I'm now glad it's there and hope you won't delete it. – Steven Landsburg Mar 18 '13 at 14:05
Thank you very much Joel! This gives me a great deal to read up on and learn about. Do you happen to know any good resources on computable analysis? It seems interesting, but the Wikipedia page is fairly short. I am sorry for asking Steven, but I asked my maths teacher at school and he wasn't sure so as I had asked a couple of questions before on StackOverflow and had very informative responses (as I have just had here) I thought it might be worth asking. – Reuben Mar 18 '13 at 16:43
Here is one standard reference on computable analysis:…. Another is:…. – Joel David Hamkins Mar 18 '13 at 16:52
See also this MO question:… – Joel David Hamkins Mar 18 '13 at 19:40

Given any infinite sequence of integer pairs $(x_i,y_i)$ for $i \ge 0$ with distinct $x$ values, there is a unique sequence of polynomials $p_i(x)$ so that $p_i$ has degree no more than $i$ and $p_j(x_i)=y_i$ for all $j \ge i.$ So one might be tempted to say that the $p_i$ are converging to a function given by a sort of power series $P(x)$. It is also true that if the $y$ values are given by a polynomial $f(x)$ of degree $d$ then $p_i=f$ for all $i \ge d.$

However, $p_i$ will typically give no information about any values $y_j$ for $j \gt i$ and the $p_i$ will simply become more and more unwieldy.

In the simplest case that $x_i=i$ one will have $p_i=\sum_{j=0}^{i}c_j\binom{x}{j}$ and $$P(x)=\sum_{j=0}^{\infty}c_j\binom{x}{j}$$ where each $c_i$ is chosen to be whatever will make $P(i)$ equal to $y_i$ : $c_i=y_i-p_{i-1}(i)$

So the values $[0, 0], [1, -1], [2, 2], [3, -3], [4, 4], [5, -5], [6, 6], [7, -7], [8, 8], [9, -9],\cdots$ would yield coefficients $c_i$ starting out $0, -1, 4, -12, 32, -80, 192, -448, 1024, -2304$ Maybe you recognize those coefficients but perhaps the rule switches to something else starting with $x_{10}.$

share|cite|improve this answer
Thank you for a concrete explanation, it has improved my understanding of the issue much. – Reuben Mar 18 '13 at 16:59
Also, think of training your universal function to answer $x=n$ given $x=n$. Then you have $10$ data points indicating the identity function. Now get it to answer $x=n$ given $n=x$ so you have 10 more data points $(2^{n+7}3^55^1,2^13^55^{n+7})$ This is not something a polynomial does well and your other equations are all broken until you go to a degree $19$ polynomial. Going up to two digits only increases the complexity. Consider $x-0=n$ if you wish. – Aaron Meyerowitz Mar 18 '13 at 18:23

Not the answer you're looking for? Browse other questions tagged or ask your own question.