Re: ESSAY: Program length, Omega and Friendliness

From: William Pearson (
Date: Tue Feb 28 2006 - 07:24:15 MST

> The approach I am going to take would be change the problem into an
> equivalent non-hanging problem.
> while (1)
> {
> output = performFunction(input)
> }

A quick note, the approach I will really end up taking is close to the
following. It has two undecidable properties it wants to maintain, not
hanging and halting of the proof mechanism (finding a provably better
program). This means there is two notions of output, one of the proof
mechanism and one of the function being performed. And so two notions
of complexity. I haven't quite got my head round these yet.

 while (1)
   output = performFunction(input)
   ( partialProofs, provenBetterProgram) =
   if provenBetterProgram != 0

 Will Pearson

This archive was generated by hypermail 2.1.5 : Wed Jul 17 2013 - 04:00:56 MDT