6
$\begingroup$

I seem to recall an academic paper from some years ago which used machine learning (possibly genetic or evolutionary programming) to predict whether a Turing Machine would halt.

By predict, I mean the standard notion in ML: minimize the error on some validation set. For simplicity, let's assume that the ML is a binary classifier, (although AFAIK the actual paper may have framed it as a regression problem).

The notion is then not 'solving' the Halting Problem (which we know is impossible), but rather using ML to agree with an Oracle that knows the answer on the training (and validation) set.

However, I haven't been able to find anything so far.

Does anyone know of a reference?

$\endgroup$
  • 2
    $\begingroup$ What do you mean by "predict"? It's not possible to solve the Halting problem using ML. $\endgroup$ – Raphael Aug 8 '16 at 13:40
  • $\begingroup$ Edited for clarity. $\endgroup$ – NietzscheanAI Aug 8 '16 at 13:45
  • 1
    $\begingroup$ "minimize the error on some validation set" -- of course you can train something on finite samples. That doesn't mean it does anything reasonable on the whole input space; in fact, we know it can't do so here. $\endgroup$ – Raphael Aug 8 '16 at 18:49
  • 1
    $\begingroup$ Sure - I'm just looking for the paper, so I can see what they said about precisely that issue and where it was published. $\endgroup$ – NietzscheanAI Aug 8 '16 at 18:50
7
$\begingroup$

After some digging around, I finally came across the original paper.

Regarding applications of a (necessarily fallible) predictor of halting - one possibility is to use it as a heuristic in some wider heuristic process, for example in the generation of Turing-complete programs for Genetic Programming.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.