[Math] Translate Programming code to Math

computer science

Almost all mathematical formulas functions etc can be translated to programming codes, can it be done in reverse i.e. code to math?

Is it possible to convert simple programming codes (programs that are not hardware or software specific) to mathematical formulas and functions? i.e. is it possible to translate a program which remove vowels from a string?

I think 'simple programming codes' is a vague statement so I have given the example of type of programs.

Best Answer

I'll provide an example of, say, removing the third to last letter from a string. You could first translate each letter into a number through a process similar to Godel Coding. Say you use something like ASCII, and each letter gets turned into three digits. So, "math" would become 109097116104, because 109 is ASCII for m, 097 ASCII for a, etc.

If you set $x_3 = 109$, $x_2 = 097$, $x_1 = 116$, $x_0 = 104$, and let $x = 1000^3 x_3 + 1000^2 x_2 + 1000 x_1 + x_0$, so that $x$ denotes the string "math". If we want $y$ to denote "math" with the second letter removed, we let $y = 1000^2 y_2 + 1000 y_1 + y_0$ and add the restraints $y_2 = x_3$, $y_1 = x_2$, and $y_0 = x_0$. If we restrict $0 \le x_i < 1000$ and $0 \le y_i < 1000$ for all $i$, then applying this complicated system of equations on $x,y,x_0,x_1,x_2,x_3,y_0,y_1,y_2 $ gives a system of equations that forces the string denoted by $y$ to be the string denoted by $x$, but with the second letter removed. This system of equations can be transformed easily into one huge diophantine equation.

Through a similar process, it turns out any problem solvable by a turing machine can be transformed into a huge diophantine equation. However, it is not a simple procedure.

Related Solutions

[Math] a good language to develop in for simple, yet customizable math programs

I'd suggest to look into python because it's a modern language with an easy syntax.

Also for mathematical application you could look at sage. That's basically an extension of python which provides an interface to many mathematical programs (among others maxima, octave, gap, R, etc..).

This is also convenient because you have a "built-in" representation of mathematical objects. For example, if you want to manipulate polynomials, you don't need to define a class to represent polynomials. You do something like that:

def gcd(P,Q):
    F, G, R = P, Q, P % Q

    while (R != 0):
        F, G, R = G, R, F % G

    return G

print gcd(5,6)    # Compute gcd of integers

R.<x> = PolynomialRing(QQ)
P, Q = x^7-1, x^14-1

print gcd(P,Q)    # Compute gcd of polynomials

[Math] Does the recursion theorem give quines

The Wikipedia article has an explicit example in LISP of how to use the method of the proof to generate a Quine. The proof of the recursion theorem is entirely constructive and syntactic, so it can be implemented in any other Turing complete language.

Looking at the section there called Proof of the second recursion theorem:

The programming language will be able to implement the function $h$ defined at the top of the proof, because $h$ is computable and the language is Turing-complete
- In particular, $h$ is a program that takes as input a program (source code) $x$ and produces as output a program (source code) $h(x)$. The source code given by $h(x)$ does the following: on input $y$, $h(x)$ first simulates the running of source code $x$ with itself as input. If that produces an output $e$, then $h(x)$ proceeds to simulate running the program $e$ with input $y$.
- The program $h$ can be implemented in any Turing complete language; the main point is that you have to write an interpreter for the language within the language itself, so that $h(x)$ can use that interpreter as a subroutine to simulate running any source code on any input.
Furthermore, the language will be able to implement $F \circ h$ because $F$ is also computable. To do this, just use the source code for $h$ and then use its output as an input to the source code for $F$.
Let $e_0$ be a specific program (source code) that implements $F \circ h$. Let $e = h(e_0)$.
Then the program $e$ will compute the same function as the program $F(e)$, as the proof shows.
Thus, in the special case where $F(e)$ returns source code for a program that does nothing but return $e$, because program $e$ computes the same function as $F(e)$, program $e$ also returns the source code for $e$ when it is run.
- In fact, program $e$ does something stronger than computing the same function: examining the proof show that program $e$ actually computes the source code for $F(e)$ and then runs (or interprets, or simulates) that. So if $F(e)$ has side effects, like printing something, $e$ has the same side effects.

For any Turing complete language, you can follow this sequence of steps to get a Quine in that language.

The interest for people who write Quines is generally to make ones that are shorter than the ones obtained by this method. The proof of the second recursion theorem is more general than is needed for that special purpose, and the Quines it generates would be very long, because the program that computes $h$ includes, in most cases, an interpreter for the language at hand. So to implement $h$ in $C$, you have to write a $C$ interpreter in $C$. This is why LISP gives a better example, because it is much more straightforward to interpret LISP in LISP.

Best Answer

Related Solutions

[Math] a good language to develop in for simple, yet customizable math programs

[Math] Does the recursion theorem give quines

Related Question