How Non-computability Relates To Fermat's Last Theorem (revised)

Please download to get full document.

View again

of 4
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Document Description
How Non-computability Relates To Fermat's Last Theorem (revised)
Document Share
Document Tags
Document Transcript
  How   Non-computability   Relates   To   Fermat's   Last   Theorem By David Williams Abstract Non-computable   functions   can   seem   so   quixotically   remote   from   everyday mathematics   that   we   may   imagine   they   have   little   relevance   to   more   familiar domains   of    application.   That   this   isnt   true   will   be   demonstrated   here   using   the proofs   set   forward   by   Tibor    !ado   in   his   "#$%   article   in   The   Bell   &ystem Technical   'ournal   -   On   Non-computable   functions.   (   will   apply   his   proofs   to   the   principles   governing   the   generation   of    )ythagorean triples   to   show   how   non-computable   functions*   indeed   non-computability   per se*   is   essential   to   the   logical   rigour    underpinning   +ermats   ,ast   Theorem* proved   by    ndrew   Wiles   in   "##*   which states that   there   are   no   whole   number solutions   to   the   formula/   for    all   integer values   of    n0% A   Brief    Summary !ado   proved   that   there   are   well-defined   functions   which   grow   so   quic1ly   that   no explicit   formulation   of    them   is   possible.   To   aid   him   he   relied   upon   the   design   of a   rudimentary   Turing   2achine*   which   would   read   and   write   a   "   or    a   3   on   a potentially   infinite   tape*   then   shift   one   step   to   the   left   or    right   before   continuing or    stopping.   The   behaviour    of    each   machine   is   governed   by   a   number    of    states which   each   have   basic   rules*   e.g.  “ )rint   a   "   if    tape   read   3*   or    else   leave   it   and then   go   to   state   4 ” .   &tate   4   would   have   its   own   rules   which   could   differ arbitrarily   from   its   predecessor.+or    a   Turing   machine   with   n   states*   it   can   be   found   that   the   number    of    possible permutations   of    instruction   sets   is/   5"6+or    example   a   single   state   can   ma1e   $7   different   machines   5or    programmes   in modern   terms6*   two   states   %389$   machines   etc.   Notice   the   number    of permutations   rises   extremely   fast   but   is   still   calculable   using   5"6.   (f    we   decide   to run   every   possible   machine   with   a   particular    number    of    states   we   will   find   that some   will   do   nothing*   some   will   loop   infinitely*   and   some   will   run   for    a   time   and then   stop.   :ach   of    them   will   also   print   any   number    of    "s   and   3   from   3   to   infinity depending   on   the   instruction   set   being   followed.  ;f    interest   to   !ado   was   the   calculation   of    the   highest   possible   number    of    "s achievable   with   each   set   of    states.   <e   defined   a   function   that   would   return   the highest   finite   score   attainable   whilst   ignoring   those   that   looped   forever.   This   is the   Busy   Beaver    function*   more   formally   1nown   as  ∑ 5n6*   and   its   non-computability   was   proved   by   !ado   in   steps   which   will   be   omitted   here   as their conclusions need only be outlined in sufficient detail for our purposes. They are as follows/56   +or    every   explicit*   monotonically   rising   function   f5n6*   the   function  ∑ 5n6   will always   increase   at   a   faster    rate   and   therefore   can   not   be   explicitly   defined.5B6   +or    every   score   in  ∑ 5n6   the   number    of    steps   that   the   winning   machine ma1es   will   always   be   either    equal   to   or    greater    than  ∑ 5n6.   With   5   6and   5B6   in   mind   we   will   now   loo1   at   the   set   containing   those   Turing machines   which   halt   and   refer    to   its   cardinality   as   N5n6.   (t   has   also   been   proven by   !ado   that   this   set*   though   not   incalculably   large*   is   still   non-computable   on account   of    the   halting   problem   proved   by   Turing   in   his   "#98   paper    On computable numbers, with an application to the Entscheidungsproblem . Turing   showed   that   it   is   impossible   to   generally   determine   which   machine   will either    halt   or    continue   indefinitely*   and   !ados   later    wor1   clearly   establishes   an equivalence   between   the   halting   problem   and   the   non-computability   of    N5n6.The   proof    of    the   non-computability   of    N5n6   goes   thus/   we   assume   that   it   is possible   to   run   all   the   machines   with   a   certain   number    of    states   and   count   each one   that   stops   after    "   step*   %   steps*   etc.   until   we   have   accounted   for    every machine   with   n   number    of    states.   ;nce   counted   this   way   we   find   we   can   obtain N5n6   for    any   n   we   choose.   =nfortunately   this   cannot   be   the   case   as   the   count must   include   the   number    of    steps   ta1en   by   the   highest   scoring   machine   which* as   we   1now   from       and   B*   is   impossible   to   calculate.   Therefore   N5n6   is   non-computable. Pythagorean   Triples We   return   now   to   +ermats   ,ast   Theorem   and   relate   it   to   all   of    the   above.   +irstly we   arrange   5"6   in   the   following   form   for    when   n>"/   5%6Notice   now   that   the   formula   for    listing   all   possible   Turing   machines   with   n>" states   has   been   expressed   as   a   possible   )ythagorean   triple   in   terms   of    the   sum of    those   machines   which   have   no   halting   instruction   5the   second   term6   and   a remainder*   )?%n*   which   represents   the   non-trivial   sum   of    machines   with   halting codes   which   either    halt   after    a   finite   number    of    steps*   or    loop   forever.    (t   is   clear    that   as 5%6   applies   to   machines   with   one   state   then   in   this   instance   it has   no   whole   number    solution.   <owever    if    we   allow   n   to   increase   inside   the brac1eted   terms   without   a   corresponding   increase   in   the   outer    powers   of    n   we find   we   can   generate   triples   of    the   form/   596   576(mportantly   in   596   and   576   the   )   terms   are   also   expressible   as   the   sum   of    two squares/   56   5$6 Non-omputable   Triples ,et   us   now   imagine   a   consequence   of    assuming   +ermats   ,ast   Theorem   to   be false.   (t   would   be   reasonable   to   assume   given   5"6   that   5%6   would   be   soluble   for many   triples   of    the   form/   +or all n0% 586(t   would   also   be   reasonable   to   assume   that   at   least   one   value   for    )?%n   could   be expressible   as   the   sum   of    two   smaller numbers of power %n   as   in   examples   56 and   5$6.   (f    this   were   the   case   we   would   be   in   a   position   to   describe the   number of    halters   and   loopers*   which   have   halt   codes*   as   a   sum   of    two %n-power whole numbers.   &uch   an   equation   would   equate   the   well-defined   formula   for    the   set   of halters   with   one   of    the two terms*   so   if    we   wished   to   establish   the   cardinality   of the   set   of    halters   N5n6   we   need   only   to   run   the   machines   associated   with   )   and count   those which halt.   (f    the   count   exceeds   the   lower    of    the   two terms   then   we may   assume   it   is   equal   to   the   larger term   and   thus   also deduce   the   cardinality of    the   set   of    non-trivially   infinite   loopers.(n   this   way   we   could   solve   many   open   problems   in   number    theory   by   running their    equivalent   Turing   machines   and   seeing   which   cardinality   they   possess.   ;f course   this   approach   is   impossible   as   establishing   the   set   of    halters   N5n6   is equivalent   to   counting   the   set   of    infinite   loopers   which   we   1now   cannot   be done.  onclusion (f    +ermats   ,ast   Theorem   had been proved false   it   would   have   implied   the constructibility   of    an   n-dimensional   shape   with   sides   corresponding*   with   well-defined   functionality*   with   the   cardinalities   of    of    the   sets   of    non-trivial   Turing halters   and   loopers* as in 586.   (t   would   also   have   implied   the   non-constructibility of    non-computable   functions   that   are   well-defined.   ;pen   questions   in mathematics   would   be   decidable   and   the   halting   problem   would   be   crac1able.   This   is   not   so   of    course*   and   +ermats   ,ast   Theorem   appears   to   support   the principle   of    non-computability.   @onversely*   non-computability   may   serve   as   a supporting   proof    of    +ermats   ,ast   Theorem.
Similar documents
View more...
Search Related
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks