StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Yes.</p> <p>I highly recommend <a href="http://www.geometer.org/mathcircles/construct.pdf" rel="noreferrer">Introduction to constructions</a>, which is a good basic guide.</p> <p>Basically you need to be able to compute with <a href="http://en.wikipedia.org/wiki/Constructible_number" rel="noreferrer">constructible numbers</a> - numbers that are either rational, or of the form a + b sqrt(c) where a,b,c were previously created (see page 6 on that PDF). This could be done with algebraic data type (e.g. <code>data C = Rational Integer Integer | Root C C C</code> in Haskell, where Root a b c = a + b sqrt(c)). However, I don't know how to perform tests with that representation.</p> <p>Two possible approaches are:</p> <ul> <li><p>Constructible numbers are a subset of <a href="http://en.wikipedia.org/wiki/Algebraic_number" rel="noreferrer">algebraic numbers</a>, so you can use algebraic numbers. All algebraic numbers can be represented using polynomials of whose they are roots. The operations are computable, so if you represent a number a with polynomial p and b with polynomial q (p(a) = q(b) = 0), then it is possible to find a polynomial r such that r(a+b) = 0. This is done in some CASes like Mathematica, <a href="http://documents.wolfram.com/mathematica/book/section-3.4.3" rel="noreferrer">example</a>. See also: <a href="http://en.wikipedia.org/wiki/Algebraic_number" rel="noreferrer">Computional algebraic number theory - chapter 4</a></p></li> <li><p>Use Tarski's test and represent numbers. It is slow (doubly exponential or so), but works :) Example: to represent sqrt(2), use the formula x^2 - 2 && x > 0. You can write equations for lines there, check if points are colinear etc. See <a href="http://xorshammer.com/2009/05/14/a-suite-of-cool-logic-programs/" rel="noreferrer">A suite of logic programs, including Tarski's test</a></p></li> </ul> <p>If you turn to <a href="http://en.wikipedia.org/wiki/Computable_number" rel="noreferrer">computable numbers</a>, then equality, colinearity etc. get undecidable.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload