From: Christian Szegedy (szegedy@or.uni-bonn.de)
Date: Thu Oct 21 2004 - 06:18:07 MDT
Eliezer Yudkowsky wrote:
>
> Presumably it also requires that the solution be correct.
Typical optimization probems come with another TM checking the
correctness. For example the graph coloring problem is defined
by:
For each graph G, produce an output, for which the following
problem returns true.
----------------- Progam:
Check whether the input is a valid coloring
-----------------
This is the whole idea of the NP complexity class: the class
of those problems, for which the correctness of solutions can
be checked in polynomial time.
> This is a problem because no consistent proof system can prove that
> the system only produces correct theorems, so no proof system can
> prove the usefulness of a faster, rewritten proof system. Unless you
> specifically state that you're trying to prove admissibility in the
> old system, rather than correctness, usefulness, or other expected
> utility criteria on the object level. Hence the need to patch the
> Godel Machine.
You will never be able to prove absolute consistency in a formal fashion.
Absolute consistency is always a hypothesis. In fact it is a physical
statement, not a mathematical one.
This archive was generated by hypermail 2.1.5 : Tue Feb 21 2006 - 04:22:47 MST