| This study suggests two learning-based artificial intelligence approaches for solving undecidable problems, problems characterized by “high expense to accurately evaluate the quality of a candidate solution.” We show that there are important problems that have this character and that the research literature has largely ignored these types of problems. We build upon the seminal work of Alan Turing and his notion of an undecidable problem. Paraphrasing Turing's definition in our context, a problem is undecidable if it is impossible to accurately evaluate the quality of a candidate solution in known finite time. We expand this notion to include many important and practical problems with the characteristic in quotes above, and give examples. This research endeavors to identify new systematic and effective solution methods for these problems.; We define and motivate a particularly important undecidable problem, denoted P, as that of finding an effective algorithm for an NP-hard problem, a focal point for our investigation. We provide a critical analysis of the only known general systematic method for undecidable problems, i.e., statistical theory that guides an experimenter to efficiently design an experiment and interpret the results. Our critical analysis focuses on the strengths and weaknesses of this experimental design (ED) theory for attacking problem P, and indicates the need for a different approach.; We propose a biologically motivated approach that can be used for P, among other undecidable problems. Simulated learning (SL) leaves it up to the researcher to select candidate solutions, but provides guidance on new and effective alternative solutions by using “schema” in the experimental results. SL is akin to response surface methodology (RSM), which uses the history of results to suggest an alternative candidate solution for evaluation. The jagged and complex response surface of problem P likely renders RSM ineffective. Evidence of the potential efficacy of SL in extracting schema from candidate solutions is gained though computational experiments with solving traveling salesperson problems. SL appears to be promising at distilling the schema of this decidable problem with complex structure (i.e., NP-hard). Initial experience with solving an undecidable problem is also provided.; We critique automated methods in the literature that can be applied to problem P. This motivates investigation of a genetic programming (GP) approach based on a kernel representation scheme. We specify the kernel in detail and show that it is capable of representing many different search algorithms from the literature. We implement the GP/kernel approach and run computational tests. Our evaluative analysis leads to suggestions for further research on automated methods for undecidable problems. |
