Leibniz, Complexity and Incompleteness

author: Gregory Chaitin, University of Auckland
published: Oct. 15, 2008, recorded: September 2008, views: 25460

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.

Lecture popularity: You need to login to cast your vote.

Description

I will discuss Leibniz's ideas on complexity (Discours de metaphysique, 1686), leading to modern work on program-size complexity, the halting probability and incompleteness. Leibniz's principle of sufficient reason asserts that if anything is true it is true for a reason. But the bits of the numerical value of the halting probability are mathematical truths that are true for no reason. More precisely, as I will explain, they are irreducible mathematical truths, that is, true for no reason simpler than themselves.

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Reviews and comments:

1 Donald DeGracia, November 3, 2008 at 2:15 a.m.:

Really brilliant lecture! This fellow is SHARP!!! Let's hear it for empirical mathematics!!

2 Matus Goljer, January 12, 2012 at 1:13 a.m.:

Thanks a lot for putting this online. Great and interesting lecture. Shame it has so few views!

3 Gregory Chaitin, July 5, 2012 at 2:11 a.m.:

For my latest views on incompleteness,
please see my 2012 book
Proving Darwin: Making Biology Mathematical.
--- Gregory Chaitin

4 meseeks, October 20, 2014 at 6:20 p.m.:

Can these results be used compute these results?

5 meeseeks, October 22, 2014 at 5:07 p.m.:

Time to calculate.
If I determine if my own consciousness is a halting problem and the answer is yes my own consciousness has halted.
If the answer is no then my consciousness is not a halting problem and my consciousness is not a halting problem.

6 meeseeks, October 22, 2014 at 5:16 p.m.:

Is this like asking what is the difference between an infinitely straight pure line and an infinitely curved pure line in two dimensions?

7 meeseeks, October 22, 2014 at 5:31 p.m.:

Any work in using something like this to increase code optimization?
Can you write a code that is simple but powerful enough to optimize code from other languages?

Write your own review or comment:

Comment:
Name:
Email address:
URL:

make sure you have javascript enabled or clear this field: