examachine at gmail.com
Fri Jan 27 09:44:54 EST 2006
On 1/27/06, Harvey Friedman <friedman at math.ohio-state.edu> wrote:
> SO, there should be profound threshold phenomenon FOR ANY REASONABLE
> Perhaps we should get to work on this...
Thanks for your fine post.
Your ideas sound quite similar to the approach of Chaitin and Calude
using algorithmic information theory.
The second approach is going to prove harder to analyze, and I do
have rough ideas about it, but please let me comment on the first
approach. If we consider the algorithmic complexity of a set theoretic
sentence with k variables, the minimal program would have to contain
on the average logk bits for just coding the number of variables.
An interesting idea I can offer at the moment is that the "core" concepts
that you mention may be interpreted as short programs, the instances of
which when composed into a larger (but still short) program, generate a
a long logical sentence (in whatever reasonable low-level language
you use). I do not assert this, it is just an idea sparked by your comments,
trying to explain why the number of variables seems more significant
than mere length.
Eray Ozkural (exa), PhD candidate. Comp. Sci. Dept., Bilkent University, Ankara
http://www.cs.bilkent.edu.tr/~erayo Malfunct: http://www.malfunct.com
Pardus: www.uludag.org.tr KDE Project: http://www.kde.org
More information about the FOM