Application Church-Turing thesis

173 Views Asked by At

I would like to give examples of problems which are solvable with an algorithm, for example the function $f$ which maps the tuple $(n,m)$ to the greatest common divisor. This map is recursive. I would do it in the following way: 1st step: If $m$ equals $0$, then $\mathrm{gcd}(n,m)=n$. 2nd step: otherwise $\mathrm{gcd}(n,m)=gcd(m,n \mod m)$.

What about the set of polynomials in one variable with integer coefficients? I want to argue that the subset of the polynomials which have an integer root is recursive.

Moreover, why is the addition and multiplication of rational numbers a recursive function? What about the exponentiation of two rational numbers?

1

There are 1 best solutions below

11
On BEST ANSWER

What about the exponentiation of two rational numbers?

I assume you mean positive rational numbers with a rational exponent.

As a formal symbol $q^r$ with related rules of calculation, it all boils down to prime factorization and rules for integer exponentiation, which are recursive in any reasonable discrete representation. However, if you mean calculation of real numbers equal to the exponentiated rationals, you will need infinite series (or more complicated things) to define a recursive sequence of rational approximations, and basic operations on the real number representation (like checking which of two expressions with rational exponentials is larger) are either not recursive or it can be difficult to prove correctness or termination of the algorithms.

The other questions are simpler. Test for an integer root of a polynomial with integer coefficients can be done by searching through divisors of the first and last coefficients, which reduces the problem to integer factorization. Addition and multiplication are done by polynomial formulas, so if you know integer addition and multiplication are recursive, this is enough to get the recursiveness of rational fractions.