Answers.Body: <p><strong>Yes.</strong></p>
  
  <p>A totally random algorithm could solve any problem given unlimited time and a perfect fitness function. All you need to do is give the GA some new random population members each generation and you're guaranteed to find the solution eventually. Even if you keep only descendants of the previous generation, setting the mutation rate and number of crossovers high enough could effectively get you random individuals.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2016-10-07T07:26:16.443Z
Answers.Text: Of course this doesn't have much to do with genetic programming. If there is a solution, you can find it with random guessing given unlimited time. I would provide you even with an bounded time algorithm: If there is a solution, you can find it by trying all possible solutions.
Answers.UserDisplayName: BlindKungFuMaster
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2016-10-07T10:16:59.250Z
Answers.Text: @BlindKungFuMaster You missed the magical words "Brute force" :)
Answers.UserDisplayName: Ankur
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2016-10-06T20:29:52.853Z
Answers.LastActivityDate: 2016-10-06T20:29:52.853Z
Answers.UserDisplayName: Nuclear Hoagie
Answers.Body: <p>As per the answer to <a href="https://ai.stackexchange.com/questions/1541/why-is-cross-over-a-part-of-genetic-algorithms/1548#1548">this AI SE question</a>,
  the presence of mutation makes a GA into a global search algorithm, i.e. it will eventually visit each point in the search space. </p>
  
  <p>How <em>efficiently</em> it will do so is indeed related to the quality of the fitness function:</p>
  
  <p>A 'perfect fitness function' could conceivably mean any of the following:</p>
  
  <ol>
  <li>A function  which takes on an optimal value iff it is applied to
  an optimal solution. </li>
  <li>A function which forms a quadratic bowl
  (Newton's method can solve this in one step).</li>
  </ol>
  
  <p>A degenerate case of 1. is a 'Needle in a haystack' function, which returns the same arbitrarily poor value everywhere that isn't an optimum, and 2. unfortunately doesn't arise very often in practice.</p>
  
  <p>Hence, the role of a well-designed fitness function is to impose a gradient on the search process, which in practice will generally lie somewhere in-between 'Needle in a haystack' and 'Quadratic bowl'.</p>
  
  <p>The presence of some form of smoothness in the fitness function is one mechanism that allows better performance than random or exhaustive methods.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2016-10-07T12:37:10.003Z
Answers.LastActivityDate: 2016-10-07T12:43:14.250Z
Answers.LastEditDate: 2017-04-13T12:53:10.013Z
Answers.UserDisplayName: NietzscheanAI
Body: <p>Obviously this is hypothetical, but is true? I know "perfect fitness function" is a bit hand-wavy, but I mean it as we have a perfect way to measure the completion of any problem.</p>
  
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2016-10-07T12:42:32.730Z
Comments.Text: Of course, you will have to then assume that a solution to the problem is indeed expressible by some element of the program space. For example, if the problem is to compute Ackerman's function, then that can't be solved by GP with a primitive recursive function set.
Comments.UserDisplayName: NietzscheanAI
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-12-07T17:44:21.943Z
Comments.Text: This question is unclear to me. What is a genetic program? Do you mean a _genetic programming **algorithm**_ (which is able to evolve programs)?
Comments.UserDisplayName: nbro
Tags: <genetic-programming>
Title: Given unlimited time and a perfect fitness function, could a genetic program solve any problem?
UserDisplayName: Tory
ThreadText: # Given unlimited time and a perfect fitness function, could a genetic program solve any problem?
  
  (Asked by: username_0 on 2016-10-06)
  
  Obviously this is hypothetical, but is true? I know "perfect fitness function" is a bit hand-wavy, but I mean it as we have a perfect way to measure the completion of any problem.
  
  **Tags:** genetic-programming
  > **Comments:**
  > **username_1**: Of course, you will have to then assume that a solution to the problem is indeed expressible by some element of the program space. For example, if the problem is to compute Ackerman's function, then that can't be solved by GP with a primitive recursive function set.  
  > **username_2**: This question is unclear to me. What is a genetic program? Do you mean a _genetic programming **algorithm**_ (which is able to evolve programs)?  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_3 on 2016-10-06. Score: 1 | Accepted answer
  
  **Yes.**
  
  A totally random algorithm could solve any problem given unlimited time and a perfect fitness function. All you need to do is give the GA some new random population members each generation and you're guaranteed to find the solution eventually. Even if you keep only descendants of the previous generation, setting the mutation rate and number of crossovers high enough could effectively get you random individuals.
  
  > **Comments:**
  > **username_4**: Of course this doesn't have much to do with genetic programming. If there is a solution, you can find it with random guessing given unlimited time. I would provide you even with an bounded time algorithm: If there is a solution, you can find it by trying all possible solutions.  
  > **username_5**: @BlindKungFuMaster You missed the magical words "Brute force" :)  
  
  ---
  
  ### Answer by username_1 on 2016-10-07. Score: 1
  
  As per the answer to [this AI SE question](https://ai.stackexchange.com/questions/1541/why-is-cross-over-a-part-of-genetic-algorithms/1548#1548),
  the presence of mutation makes a GA into a global search algorithm, i.e. it will eventually visit each point in the search space.
  
  How *efficiently* it will do so is indeed related to the quality of the fitness function:
  
  A 'perfect fitness function' could conceivably mean any of the following:
  
  1. A function which takes on an optimal value iff it is applied to
     an optimal solution.
  2. A function which forms a quadratic bowl
     (Newton's method can solve this in one step).
  
  A degenerate case of 1. is a 'Needle in a haystack' function, which returns the same arbitrarily poor value everywhere that isn't an optimum, and 2. unfortunately doesn't arise very often in practice.
  
  Hence, the role of a well-designed fitness function is to impose a gradient on the search process, which in practice will generally lie somewhere in-between 'Needle in a haystack' and 'Quadratic bowl'.
  
  The presence of some form of smoothness in the fitness function is one mechanism that allows better performance than random or exhaustive methods.
  
  
  ---
  
  