6
$\begingroup$

Say I could only perform one operation (addition) from addition I could derive subtraction by adding a negative number. Also, from addition I could derive multiplication, like $ a n $, just add $ a $ to itself $n$ times. The same for division but with negative numbers (how many times do I add a negative $a$ to itself to get to $0$. Exponenciation is glorified multiplication and there exist algorithms that use only division, addition, subtraction and multiplication to find square roots and logarithms. Sin can be expressed as a Taylor series only involving exponenciation and multiplication and addition. My question is, can every operation in mathematics (like differentiation, integration, etc.) be reduced in this way? Maybe allowing for multiplication, too, so that $i^2$ could still be -1.

$\endgroup$
  • 3
    $\begingroup$ Depends what you mean; there is, for instance, no algorithm to decide whether a computable number is $0$ (see Richardson's theorem). But, on the flip side, we can do most anything to arbitrary precision. (Though not, for instance, decide whether an algorithm terminates or not) $\endgroup$ – Milo Brandt Dec 25 '14 at 4:47
7
$\begingroup$

It's a fundamental result in theoretical computer science that there exists a universal algorithm: a computable partial function $U$ with the property that for every computable function $f$ there is an $n$ such that $$ \forall x:~ f(x)=U(n,x) $$ (Essentially, $n$ can be chosen as a program that computes the function, encoded as a number in some appropriate way, and $U$ is the function that tells how to execute programs in some programming language).

This gives at least a partial answer to the question in the title.

However, mathematics can also speak about functions that are not computable, and those are not realized by the usual universal algorithm. But if we want the case where $f$ is not computable to be handled, by fairness we should also allow $U$ to be noncomputable.

Exploring exactly how many functions we can cram into a single $U$ gets us into some twisty little foundational byways. However, it turns out that practically every function encountered in "ordinary" mathematics can be specified unambiguously by a logical formula built from addition and multiplication, the constants $0$ and $1$, and quantification over subsets of $\mathbb C^n$ and functions between such subsets. In this case but we can say in standard mathematics that there is a (non-computable) $\bar U$ such that whenever $f$ is a function with such a specification, there is a number $m$ such that $f(x)=\bar U(m,x)$.

[It is not essential exactly which restrictions we put on the kind of formula that can be used to specify $f$, but we get into foundational trouble unless there are some such restrictions -- more technically there should be a predetermined repertoire of sets that the formula is allowed to quantify over. In fact a more restricted repertoire than the one outlined above can be used, at the cost of less natural specifications for many functions.]

$\endgroup$
-2
$\begingroup$

In my college course of Numerical Analysis we did exactly this. All was reduced to the simple truth table $0+0=0$, $1+0=1$, $0+1=1$ and $1+1=0$ carry $1$.

We did integration, differential equations, eigenvalue problems, matrix operations, Chebyshev polynomials, etc

I can't say ALL math could be done as I don't know ALL the math that exists. But all the math that I have studied could be solved this way and we used just Fortran IV to do it.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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