User joe shipman - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T10:15:04Z http://mathoverflow.net/feeds/user/25424 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/11540/what-are-the-most-attractive-turing-undecidable-problems-in-mathematics/103544#103544 Answer by Joe Shipman for What are the most attractive Turing undecidable problems in mathematics? Joe Shipman 2012-07-30T20:13:51Z 2012-07-30T20:13:51Z <p>My favorite example is the halting problem for Conway's "FRACTRAN" programming language: given a finite sequence of fractions q1, q2, ...., q_n, does the procedure "starting with a given integer and keep successively multiplying by the first element in the sequence which results in the product still being an integer until none of them do" halt? In fact there is specific sequence of fractions that is quite short which can be interpreted as a Universal machine.</p> http://mathoverflow.net/questions/10535/ways-to-prove-the-fundamental-theorem-of-algebra/103539#103539 Answer by Joe Shipman for Ways to prove the fundamental theorem of algebra Joe Shipman 2012-07-30T19:58:40Z 2012-07-30T19:58:40Z <p>Thanks to Tim Chow for citing me. Technically, you don't need to show every polynomial of prime degree in F[x] has a root, you just need to show that there is a field G such that every polynomial of odd prime degree in G[x] has a root and every element or its additive inverse has a square root; then G[i] will be algebraically closed. Even more interesting, to show that all polynomials of degree d have a root, all you need is that all polynomials of degree p have a root for those p which divide d, plus the existence of <em>any</em> sufficiently large degree d' such that all polynomials of degree d' have a root (an explicit algorithm for how large d' must be is easily derivable from my proof).</p> <p>Of course, this is not a proof of the Fundamental Theorem of Algebra, what I did was identify the pure algebraic core of the requirement that a field be algebraically closed. To show that the complex numbers are algebraically closed, you still need some way of showing that real polynomials of odd prime degree have roots, which depends on the Intermediate Value Theorem or some other analytical or topological argument in all the proofs I know.</p>