There exists no algorithm for solving the quadratic equation with real coefficients neither in ℝ nor in ℂ

download pdf

last update: 10/24/2016

Σημείωση: το παρακάτω να μην ληφθεί υπόψη από τους υποψήφιους για το μάθημα της Πληροφορικής στις Πανελλαδικές εξετάσεις. Αυτή η εργασία απαιτεί πληροφορικό και μαθηματικό υπόβαθρο το οποίο δεν καλύπτεται από τα σχολικά βιβλία.

There exists no algorithm for solving the quadratic equation with real coefficients neither in ℝ nor in ℂ

Giorgos Bougioukas, 2016

georgebougioukas@yahoo.com

Abstract

This paper proves that the problem of the equality of two real constants is undecidable and as a consequence there exists no algorithm for solving the (univariate) quadratic equation with real coefficients neither in ℝ nor in ℂ.

1. Definitions and assumptions

a) An algorithm is a Turing machine.

b) Assume that an algorithm (A1) for solving the quadratic equation with real coefficients in ℝ necessarily gives an output that implies the decidability of the decision problem “is there a real solution for the given equation?” (P1), e.g:

a list, empty if there exists no real solution for the given equation, with up to two (distinct) elements, otherwise.

c) Assume that an algorithm (A2) for solving the quadratic equation with real coefficients in ℂ necessarily gives an output that implies the decidability of the decision problem “has the given equation exactly one solution?” (P2), e.g:

a list, with one element if the given equation has exactly one solution, with two elements, if the given equation has exactly two (distinct) solutions.

2. The problem of the equality of two real constants is undecidable (Thm1)

Proof

Let C(TM) be a string that encodes a Turing machine TM. For every Turing machine TM and for every input string (on the input alphabet of TM) x consider the following series:

The series above converges in ℝ as 10^-kh_C(TM),x(k)≤10^-k holds for every natural number k≥1 and the series of the sequence 10^-k converges as geometric series with common ratio 10^-1 for which it holds that |10^-1|<1. Therefore, for every Turing machine TM and for every input string (on the input alphabet of TM) x the following lemma holds:

Obviously, for every Turing machine TM and for every input string (on the input alphabet of TM) x the following lemma also holds:

Consider a Turing machine TM₁ on input (on the input alphabet of TM₁) x₁. Assuming there exists an algorithm (A3) that decides whether or not two real constants are equal,  it follows that there exists another algorithm (A4) that:

a) simulating the algorithm A3 decides whether or not it holds that (the first member of the equality below is a real constant by L1):

b) via the previous result and L2 decides whether or not the Turing machine TM₁ on input x₁ halts.

In other words, the algorithm A4 decides the halting problem, a result that contradicts Turing’s “halting theorem” (Halatsis, 2003). We reached a contradiction because we assumed that there exists an algorithm such A3. Therefore, there exists no such algorithm. ▪

3. There exists no algorithm such A1

Proof

Assuming that there exists an algorithm such A1, via the assumption b) in section 1, it follows that there exists another algorithm (A5) that simulating the former, given any quadratic equation with real coefficients, decides the decision problem P1. If the form of output of the algorithm A1 is identical with the one in the example of the assumption b) in section 1, then the algorithm A5 decides P1 as follows:

– If the algorithm A1 gives as output a non-empty list – i.e there exists a real solution for the given equation – then gives as output “True”.

– Otherwise, if the algorithm A1 gives as output an empty list – i.e there exists no real solution for the given equation – then gives as output “False”.

Let r,s be real constants and d=|s-r|. Consider the following quadratic equation with real coefficients:

Given an instance of the problem P1 consisting of E1, the algorithm A5 gives the following output:

– Either “True”, i.e there exists a real solution for E1 – therefore, letting Δ be the discriminant of E1:

– Or “False”, i.e there exists no real solution for E1 – therefore, letting Δ be the discriminant of E1:

The real constants r and s have no particular properties. The same is true for the algorithm A5, except that it uses the output of the algorithm A1, which has also no particular properties, except the assumed form of its output. Therefore, for all constants s, r ∈ ℝ the equation E1 can be constructed and given as input to the algorithm A5 whose output then implies that either s=r or s≠r, which contradicts with Thm1. We reached a contradiction because we assumed that there exists an algorithm such A1. Therefore, there exists no such algorithm. ▪

4. There exists no algorithm such A2

Proof

Assuming that there exists an algorithm such A2, via the assumption c) in section 1, it follows that there exists another algorithm (A6) that simulating the former, given any quadratic equation with real coefficients, decides the decision problem P2. If the form of output of the algorithm A2 is identical with the one in the example of the assumption c) in section 1, then the algorithm A6 decides P2 as follows:

– If the algorithm A2 gives as output a list with one element, then gives as output “True”.

– Otherwise, if the algorithm A2 gives as output a list with two elements, then gives as output “False”.

Let r,s be real constants and d=|s-r|. Consider the quadratic equation with real coefficients E1.

Given an instance of the problem P2 consisting of E1, the algorithm A6 gives the following output:

– Either “True”, i.e there exists exactly one complex solution for E1 in ℂ– therefore, letting Δ be the discriminant of E1:

– Or “False”, i.e there exist exactly two (distinct) complex solutions for E1 in ℂ– therefore, letting Δ be the discriminant of E1:

The real constants r and s have no particular properties. The same is true for the algorithm A6, except that it uses the output of the algorithm A2, which has also no particular properties, except the assumed form of its output. Therefore, for all constants s, r ∈ ℝ the equation E1 can be constructed and given as input to the algorithm A6 whose output then implies that either s=r or s≠r, which contradicts with Thm1. We reached a contradiction because we assumed that there exists an algorithm such A2. Therefore, there exists no such algorithm. ▪

References

Halatsis C. (2003). Themeleioseis Epistimis I/Υ, Volume II – Theoria Ypologismou. Patras, Hellenic Open University.