A formula is a string of symbols, arranged according to mathematical grammar.
A function is a mathematical object that plays a role in arithmetic operations like "evaluation" or "composition". A key point is that if $f$ and $g$ are expressions that denote two functions with the same domain and codomain, and we have $f(x) = g(x)$ for every $x$ in the domain, then $f$ and $g$ denote the same function.
So, in your example of functions $f$ and $g$ on the set $\{ -1, 0, 1 \}$, it is indeed true that $f=g$.
Some examples of mathematical grammar
Let $f$ be a variable that denotes a function on the reals. Let $x$ be a real-valued variable. Then:
- $f$ is a function.
- $f(x)$ is a real number.
- $x^2 + 3$ is a real number. In particular, it is not a function. Unfortunately, people are frequently grammatically incorrect on this point. :(
- $f(x) = x^2 + 3$ is an equation that relates two real numbers.
and all of the bullet points above are examples of formulas.
Recall that I mentioned functions were 'defined' pointwise: if two functions solve "$f(x) = x^2 + 3$ for all $x$" for $f$, then they must be the same function. Because of this, we can use equations like this as a way to specify functions.
But as you note, if two different formulas for the right hand side actually give the same values when you substitute values from the domain, then the functions so defined will be the same.
Incidentally, it is possible to define functions directly rather than pointwise, although it often isn't pleasant. e.g. the function $f$ defined above is given by
$$ f = p \circ ((\mu \circ \Delta), c_3) $$
where I'm using the notation
- $\Delta$ is the diagonal function $\Delta(x) = (x, x)$
- $\mu$ is the multiplication function $\mu(x,y) = xy$
- $p$ is the addition function $p(x,y) = x+y$
- $c_3$ is the constant function $c_3(x) = 3$
- $(,)$ is a binary operation on functions; it's defining property is $(g,h)(x) = (g(x), h(x))$. I don't actually know of standard notation for this; sometimes I see $\times$ in place of $,$.
- $\circ$ is composition of functions: $(g \circ h)(x) = g(h(x))$.
The question you asked is more of a philosophical one instead of a mathematical one. Your question depends on the more general and fascinating question, “What is an algorithm?” Let me explain:
Everything involving computer science and computation in general can be thought of in terms of algorithms: recursive functions, programming languages, programs, computers, operating systems, etc. In the early days, the notion ‘all good algorithms can be translated into some halting Turing machine’ would have been widely accepted. Today, however, halting Turing machines do not maintain the high status they once held. There is an apparent information gap when we try to reduce so called interactive and parallel algorithms into halting Turing machines. Intuitively this can be understood as trying to reduce a windows operating system into a halting Turing machine (sounds ridiculous right?). The ridiculousness of this task stems from the fact that, ideally, an operating system like windows should never halt. You don’t want to be on Microsoft word and suddenly the algorithm ‘halts’ without being given specific instructions. Operating systems are definitely algorithms (a system of specific instructions for given inputs), but for long drawn out projects we might want our operating system to run indefinitely. So in regards to your question “Must an algorithm terminate?” in my personal opinion the answer is no. Similarly, in regards to the question, “Are all algorithms translatable into some halting Turing machine?” my answer is also no.
Many of the ideas I have suggested here were brought to my attention by the work of algorithm master Yuri Gurevich (Russian mathematician and computer scientist who now works for Microsoft). Gurevich has attempted to generalize the concept of algorithm with something he calls ‘abstract state machines’: a system for formalizing algorithms including the non-Turing-machine-convertible algorithms (like interactive and parallel algorithms). ‘Abstract state machines’ have been met with wide acclaim and there are learned societies focused solely on them.
To find more information on the work of Yuri Gurevich check out these two lectures:
Yuri Gurevich, Church Turing Thesis: Story & Recent Progress (2009)
https://www.youtube.com/watch?v=7XfA5EhH7Bc
Yuri Gurevich, What’s an Algorithm? (2011)
https://www.youtube.com/watch?v=FX2J24u92GI
Best Answer
An algorithm is in its most general definition: a way of achieving a desired goal. Formula are merely recipes or components.
Example: The actual method of baking bread with steps is an algorithm:
in here would be formula such as the formula for the bread, what ingredients etc...
The quadratic formula is just that: a formula for solving quadratic equations
An example of an algorithm for solving quadratics would be:
get quadratic: call a the coefficient in front of x^2, b the coefficient in front of x and c the constant coefficient.
evaluate quadratic formula (both + and - versions) on given a, b and c
simplify
This algorithm solves the actual problem... whereas the formula is a tool used in the process.