Does there exist a function (however complex) which given an input in the form of any problem which can be solved in a rigorous and non-random way can return the solution to that problem. [closed]

Question

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!

Answer 1

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.

Answer 2

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