Archive for March, 2007

Some aditional resources containing some of my first ideas on computability and the mind, and on universality in real computation

Friday, March 16th, 2007

A powerpoint presentation I used for supporting my talk at the Complexity, Society and Science 2005 Conference, University of Liverpool, U.K. is available here:    It is related to my paper “On the possible Computational Power of the Human Mind” recently published as a book chapter in a World Scientific book (see 2 posts below).

And a powerpoint presention in English that I prepared for Gregory Chaitin when I met him in his office at the T.J. Watson Research Center in New York in 2006 containing the main ideas from my French paper On Universality in Real Computation is available here . In it I define concepts like intrinsic, relative and absolute universality. Greg liked my notion of the  “universal jump operator”.

Back from Prague

Thursday, March 15th, 2007

Originally uploaded by hzenilc.

Amazing…  looking for a cybercafe located close to the Charles Bridge I stumbled upon Johannes Kepler’s home in Prague from the time when he was invited there by Tycho Brahe. The building now standing is not that old so it may not be the original one in which Kepler lived. But he actively worked  in the Czech capital for twelve years, from 1600 to 1612,  when he formulated his 3 laws of planetary motion. There are 2 plaques at the location, one on the facade of the building, and the other inside,  in the entrance passageway. At the center of the passageway  is a monument representing the planetary orbits.  Tourists and other passersby completely fail to notice either the plaques or the monument.

If you would like to brush up on  Kepler’s laws, I wrote a popular science article some years ago for the National University of Mexico (UNAM), which is available here (in Spanish). My final paper (mémoire du cours) for one of my master’s courses– “History of Physics”– at the Ecole Normale Supérieure (Ulm) was an analysis of some of  the most obscure passages in Kepler’s  “Mysterium Cosmographicum” which I  especially like for its proposal that the distance relationships between the planets could be understood in terms of  the Platonic solids (which by the way turned out to be a good approximation).

Even though I took many pictures (among them pictures of the plaques and the monument which I will provide upon request to anyone who may be interested) I couldn’t imagine  a better picture to post here than the one I took of the  celebrated and beautiful Prague astronomical clock on the Old Town Hall. It is unique in being the oldest clock operating on its original clockwork–from the time of its construction to the present, a total of six centuries.   Even the astronomical dial shaped like an astrolabe survives in its original form. More information about it is available at Wikipedia here. The clock was operational many years before Kepler was born, so  looking at it I wondered how many times he would have stood contemplating it during his time in Prague. For my part I dined every day for a whole week at the Prince Hotel from where I could easily admire both the clock and the awesome gothic-style Tyn’s Church.

The close-up  of the clock appearing here in my blog and in Wikipedia (currently) was taken by me on February 22nd 2007 and  released, together with other photos on the same page,  under a Creative Commons license. So do help yourself if you like any of them.

My complete picture gallery from Prague is here.

The Czech word for clock is “Orloj,” from the French “horloge”. Czech is  rather interesting  in that despite being a Slavic language and thus closely related to Russian, it, like Slovak and Polish,  uses the Latin alphabet instead of the Cyrillic.

An intriguing fact about declensions in  such languages is that in almost all cases all permutations of words in a clause are possible and have different meanings. So one can generate phrases by combinatorial means and produce sentences that actually make sense!

On the possible Computational Power of the Human Mind

Tuesday, March 13th, 2007

My paper On the possible Computational power of the Human Mind (co-authored with my BS thesis advisor Francisco Hernández-Quiroz of the Math Department of the National University of Mexico [UNAM], which I delivered as a lecture 2 years ago at the Complexity, Science & Society 2005 Conference at the University of Liverpool, U.K.) has been recently published by World Scientific as a book chapter. It is available from World Scientific at ; also as a paper or from Amazon.
The book is edited by Carlos Gershenson, Diederik Aerts (Brussels Free University, Belgium) & Bruce Edmonds (Manchester Metropolitan University Business School, UK).

Introduction: Scientific, technological, and cultural changes have always had an impact upon philosophy. They can force a change in the way we perceive the world, reveal new kinds of phenomena to be understood, and provide new ways of understanding phenomena. Complexity science, immersed in a culture of information, is having a diverse but particularly significant impact upon philosophy. Previous ideas do not necessarily sit comfortably with the new paradigm, resulting in new ideas or new interpretations of old ideas.In this unprecedented interdisciplinary volume, researchers from different backgrounds join efforts to update thinking upon philosophical questions with developments in the scientific study of complex systems. The paper contributions cover a wide range of topics, but share the common goal of increasing our understanding and improving our descriptions of our complex world. This revolutionary debate includes contributions from leading experts, as well as young researchers proposing fresh ideas.Contents:* Restricted Complexity, General Complexity (E Morin)* Complexity Science as an Aspect of the Complexity of Science (D Mikulecky)* On the Importance of a Certain Slowness (P Cilliers)* Simplicity Is Not Truth-Indicative (B Edmonds)* Why Diachronically Emergent Properties Must Also Be Salient (C Imbert)* Some Problems for an Ontology of Complexity (M McGuire)* Physical Complexity and Cognitive Evolution (P Jedlicka)* Informational Dynamic Systems: Autonomy, Information, Function (W Riofrio)* The Complexity of Information-Processing Tasks in Vision (J Symons)* On the possible Computational Power of the Human Mind (H Zenil & F Hernandez-Quiroz)and other papers

Daniel Dennett’s new thought experiment using Steve Pinker as subject…

Thursday, March 8th, 2007

An interesting thought experiment conceived by Daniel Dennet and recently published in the Time magazine.

Collections of axioms and information on theories dependency

Saturday, March 3rd, 2007

List of Axioms from Computer Science Department, University of Miami
Documentation, Computer Science Department, University of Miami
List of axioms collected from Wikipedia.
MBase: A Mathematical Knowledge Base. A collection of definitions, theorems and proofs.
The Mathematical Atlas.
Proof symbolic visualizations, University of Texas.

“The ways of paradox”: Quine on Berry’s paradox.

Saturday, March 3rd, 2007

“Ten has a one-syllable name. Seventy-seven has a five-syllable
name. The seventh power of seven hundred seventy-seven has a name
that, if we were to work it out, might run to 100 syllables or so;
but this number can also be specified more briefly in other terms. I
have just specified it in 15 syllables. We can be sure, however, that
there are no end of numbers that resist all specification, by name or
description, under 19 syllables. There is only a finite stock of
syllables altogether, and hence only a finite number of names or
phrases of less than 19 syllables, whereas there are an infinite
number of positive integers. Very well, then ; of those numbers not
specifiable in less than 19 syllables, there must be a least. And
here is our antinomy : the least number not specifiable in less than
nineteen syllables is specifiable in 18 syllables. I have just so
specified it.
The antinomy belongs to the same family as the antinomies that have
gone before. For the key word of this antinomy, “specifiable”, is
interdefinable with “true of”. It is one more of the truth locutions
that would take on subscripts under the Russell-Tarski plan. The
least number not specifiable-0 in less than nineteen syllables is
indeed specifiable-1 in 18 syllables, but it is not specifiable-0 in
less than 19 syllables ; for all I know it is not specifiable-0 in
less than 23.”

By the way, it seems that Russell thought Berry’s number was 111,777.

Book on self-reference (comprising papers by various contributors)

Saturday, March 3rd, 2007

Table of contents and introduction:

On single and shortest axioms for Boolean logic

Saturday, March 3rd, 2007

Both the philosopher Charles Sanders Peirce in 1880 and the American logician H. M. Sheffer in 1913 realized that the truth-functions of elementary logic could all be defined from a single operation. The Sheffer stroke, also known as the Nand operation, is a logical operator with the following meaning: p Nand q is true if and only if not both p and q are true. It is named for Henry M. Sheffer, who proved that all the usual operators of Boolean algebra (Not, And, Or, Implies) could be expressed in terms of Nand. There is another logical operator which is able to express all the others: Nor [A set of five independent postulates for Boolean algebras, with application to logical constants. Transactions of the American Mathematical Soc. 14 (1913), pp. 481-488]. In 1933, Edward Huntington proposed an alternative set of axioms for Boolean algebra, consisting of associativity and commutativity plus Huntington’s axiom:

!( !x [Or] y) [Or] ( !( !x [Or] !y ) = x

Huntington showed that the three axioms together imply the axioms of Boolean algebra. Sometime after, Herbert Ellis Robbins also found a single axiom:

!( !( x [Or] y) [Or] ( y [Or] !x )) = x

that he conjectured (when taken  together with associativity and commutativity) implied that of Huntington, so that Robbins algebras are equivalent to Boolean algebras. The proof was finally delivered in 1996 by William McCune, using his theorem prover EQP. See:

Gina Kolata, Computer Math Proof Shows Reasoning Power, The New York Times, 1996.

Tutorial on Automatic Reasoning and Theorem Proving related to the course MAT 504, Topics in Logic, for the Spring term of 1997 from prof. Edward Nelson

As a result of an exhaustive and systematic computer exploration undertaken by Stephen Wolfram looking for the shortest single axiom equivalent to the axioms of Boolean algebra. Wolfram found among 288684 a single formula (up to other equivalent of the same size) with 6 Nands and 3 variables. It then turns out that Wolfram’s axiom:

(((x [Nand] y) [Nand] z) [Nand] (x [Nand] ((x [Nand] z) [Nand] x))) = z

is equivalent to the axioms of Boolean algebra and the shortest (in the number of operators and variables) single axiom equivalent to Boolean algebra (Wolfram 2002, pp. 808-811 and 1174).

In the NKS notes at the end of the book there is an account that around 1949 Carew Meredith found the axiom system (NKS page 1173):

f[f[a, f[b, c]], f[a, f[b, c]]] = f[f[f[c, a], a],f[f[b, a], a]]f[f[a, a], f[b, a]] ==a

And in 1967 George Spencer Brown found:

f[f[a, a], f[f[b, b], b]] ==af[a, f[b, c]] = f[f[f[f[c, c], a], f[f[b, b], a]], f[f[f[c, c], a], f[f[b, b], a]]]

and again Meredith in 1969:

f[a, f[b, f[a, c]]] = f[a, f[b, f[b, c]]]f[f[a, a], f[b, a]] = af[a, b] == f[b, a]

Carew Meredith spent a long time studying somewhat similar forms. Meredith’s interest in short axioms came originally from Lukasiewicz.

More references:

More bibliographical references (Meredith and Prior 1968 and Meredith 1969b are the main ones on equational logic, and Meredith 1951 contains the six-character single axiom that Prior described as ‘sensational’):

  • – Meredith, C.A. 1951. ‘On an Extended System of the Propositional Calculus’. Proceedings of the Royal Irish Academy, vol. 54 Sect. A, 37-47.
  • – Meredith, C.A. 1953a. ‘Single Axioms for the Systems (C,N), (C, 0), and (A, N) of the Two-Valued Propositional Calculus’. Journal of Computing Systems, vol. 1, 155-164.
  • – Meredith, C.A. 1953b. ‘A Single Axiom of Positive Logic’. Journal of Computing Systems, vol. 1, 169-170.
  • – Meredith, C.A. 1958. ‘The Dependence of an Axiom of Lukasiewicz’. Transactions of the American Mathematical Society, vol. 87, 54.
  • – Meredith, C.A. 1966. ‘Postulates for Implicational Calculi’. Journal of Symbolic Logic, vol. 31, 7-9.
  • – Meredith, C.A. 1969b. ‘Equational Postulates for the Sheffer Stroke’. Notre Dame Journal of Formal Logic, vol. 10, 266-270.
  • – Meredith, C.A., Prior, A.N. 1963. ‘Notes on the Axiomatics of the Propositional Calculus’. Notre Dame Journal of Formal Logic, vol. 4, 171-187.
  • – Meredith, C.A., Prior, A.N. 1968. ‘Equational Logic’. Notre Dame Journal of Formal Logic, vol. 9, 212-226.