Re: Complete Arithmetic?

From: Russell Easterly (logiclab_at_comcast.net)
Date: 01/03/05 

Date: Mon, 3 Jan 2005 12:59:06 -0800

"David C. Ullrich" <ullrich@math.okstate.edu> wrote in message
news:sr8jt0t9p8b9tk0pbul3qg4kqjggd2fngu@4ax.com...
> On Mon, 03 Jan 2005 15:14:36 +0100, Steven <steven2000@despammed.com>
> wrote:
>
> >> (Some computer guys down the hall have some thoughts
> >> that seem quite far-fetched to me about using
> >> "genetic programming" to solve some unsolved problem
> >> in mathematics. They were planning on going for
> >> Fermat's Last Theorem until I told them that that
> >> had been done...)
> >Building automated theorem prover is a great challenge, and much research
> >has been done here, but still the abilities are way beyond expectations.
> >The more interesting axiom systems are not complete, but this is not such
a
> >big problem; rather the computational complexity is. Going for Fermat's
> >theorem seems very naive, if you consider the abilities of todays
automated
> >theorem prover... they usually fail with theorems that can be shown by
> >schoolkids.
> >Genetic programming can be regarded as a buzzword. There are rumours
about
> >very successful applications of that approach, but I think they are
> >obtained with "Core Wars", an assembly language game with about 10
> >commands.
> >Theorem provers are useful to verify formal proofs, and to do a lot of
> >rather trivial proving; but it still requires a human to do math.
>
> In case it wasn't clear, that all seems perfectly correct to me - I
> told the guys as much, (except for the bit about genetic programming
> being a buzzword), but they've been very successful in using genetic
> programming to play blackjack and so they're determined to move
> on to unsolved mathematics...

"Genetic" programming is simple enough.
You generate 100 random programs.
You test them and pick the top ten best scores.
Then you "mutate" the winning programs by mixing,
matching, and/or shuffling the winning programs.
This gives you 100 new programs.
Repeat the process 1000 times and you end up with
a "random" program that scores well.

If you want to use genetics to solve math problems,
it might be best to pick a problem that is easy to "mutate".
Realize that a genetic program is "good" but may not be "best".
You want a problem that can be "proved" in a large number of ways.
I would choose some Turing Machine related problem.
TMs are easy to "mutate" and there can be a lot of TMs
that "solve" the same problem.
For example, the Busy Beaver problem (smallest TM that halts
after N steps) might be a good problem to attack.

Russell
- 2 many 2 count

Relevant Pages

  • Re: Characterizing complexity
    ... Michael Ragland wrote: ... Under what conditions biological evolution couldn't do the same? ... genetic programming it seems to me ...
    (sci.bio.evolution)
  • Re: OT: Newbie question re: genetic algorithms/AI
    ... > I've recently started trying to put some of my ideas regarding programming ... the lieftime of the robot in your example below). ... This looks more like genetic programming than like a genetic algorithm. ...
    (comp.lang.lisp)
  • Re: Expert Systems: Is Human Competence Relevant?
    ... problem with a completely different engine. ... programming, you don't simply evolve the entire program in one shot. ... The genetic programming system doesn't evolve the whole program; ... It just does all the gruntwork, and the humans sew the ...
    (rec.arts.sf.science)
  • Re: compilation timing questions
    ... >>I am currently writing my thesis for a microbiology PhD on viral ... > This is not the way to do genetic programming. ... >>GNU compiler if required or some other alternative if there is one! ...
    (alt.comp.lang.learn.c-cpp)
  • Re: The n-knights problem
    ... but that the heuristics used are so simple and fail so often. ... Several months ago I dabbled in genetic programming. ... diud not have knights, and try to derrive a generalising rule for. ... a theorem prover with mathematical induction, ...
    (comp.lang.prolog)