Computability: theoretical or practical?

Alan Turing defined in 1936 the now well known "Turing Machine" to define computation. A Turing Machine is actually an abstract mathematical construction, which cannot be fully materialized, since it requires an infinite tape (memory). Nevertheless, people have been discussing their brains out on whether the human mind (whatever that may be) is computable or not. This is because people believe that if whatever our brains or minds do is computable, then (in principle) it could be modelled in a computer, thus reaching the ultimate goal of artificial intelligence: a machine with the same intellectual abilities as a human (whatever that may be).

Still, computability as we understand it, i.e. Turing computability, i.e. a function that a Turing machine can perform, is only computability in theory. In practice, there are Turing-computable numbers that are not computable in practice by our computers, since there would not be enough time in the universe to calculate them, or memory to store them. And there are also non-Turing computable operations (such as the halting function of a Turing Machine) that are computable in practice (for the case of halting functions, cheating with an "oracle", i.e. knowledge about the machine outside the machine).

So, to conclude, I believe we should really distinguish Turing computation (calculated by abstract Turing machines) from pragmatic computation (calculated by any actual computing device). Then we can subdivide pragmatic computation depending on the device itself, i.e. there will be functions pragmatically computable with an abacus, some more with a PC, some others with DNA, some others with a brain...

P.S. For those interested on whether a digital computer (or robot) will be able to perform the same functions as a human, the answer is: we'll know if it's possible only when we see it... (which is actually what the Turing Test (1950) proposed...)

50 years of AI

The term "Artificial Intelligence" (AI) was coined at a conference in Dartmouth College, NH, in the summer of 1956, so this year has seen several celebrations, e.g. in Boston, Monte Verità, Paris... so Brussels couldn't be left behind!

The AILab of the VUB organized a one day event at the Royal Flemish Academy for Arts and Sciences, with invited talks by people who have done advancements in AI in Flanders... so it was basically VUB people (i.e. ex-students of Luc Steels) and a couple from Leuven. You can see the full info here (in Dutch).

So, during and after the presentations, I realized how the expectations of AI have changed. In the 50's, people were predicting that we would have robots with humanlike intelligence in a few decades. In the 80's, a new wave of AI began to spread, namely with behaviour-based systems, neural networks, dynamical systems theory, and artificial life. Many of these were also aiming at humanlike intelligence (from the bottom-up), severely criticizing the approaches of GOFAI (good old fashion AI, based on symbol manipulation, knowledge modelling, planning, etc.). The fact is that "new AI" expectations haven't been reached anyway, and now most people make hybrid systems. This is because knowledge-based systems, behaviour-based system, connectionist systems, conceptual systems, etc. aim at different aspects of cognition. (See Cognitive Paradigms: Which One is the Best? Cognitive Systems Research 5(2):135-156, June 2004).

Then, can we say that AI has been a failure???

Not at all! It didn't fulfil its sexiest expectations, but it has made great technological advances, and not only in playing chess! The thing is that it has been absorbed by other domains, which now use AI techniques, without calling them AI... In engineering, computer science, linguistics, genomics entertainment... Many cars and factories have AI-based self-diagnostic systems, all the automatic translators and recognizers are AI. Special effects in films, strategies in games, multi-agent systems, modern programming languages and techniques... all of them have AI roots. Only that we don't call them AI anymore...


A new Republic in Mexico

Yesterday, November 20th, 96th anniversary of the Mexican Revolution, Andrés Manuel López Obrador took protest as the legitimate president of Mexico. Since the circles of power have corrupted the national institutions and the media, culminating with the presidential elections fraud last July 2nd, more than a million Mexicans, of which several were representing many others, gathered last September at a National Democratic Convention, and elected López Obrador as the legitimate president (well, he had won already, but since the electoral institutions and tribunals were corrupted, they gave the victory to the puppet Felipe Calderón, who will attempt to take possesion of a spurious presidency on December 1st).

The new legitimate government will be defending the rights of the majority of Mexicans, living in poverty and "forgotten" by the people in power (they have not forgotten, they are just being unmercifully exploited). For example, the President proposes to the Congress the budget for the next year. López Obrador will present an alternative budget, promoted by the congressmen from the parties that support him, redistributing expenses in the areas that require the most, such as education, healthcare, pensions, etc.; and reducing the high salaries of politicians in the federal government (As a major of Mexico City, López Obrador did this for the buraucrats of the City, using the saved money to develop the City in spite of the cuts to the city's budget by the federal government). Other modifications to the Constitution will be suggested to the Congress, trying to bound the privileges of those in power and to develop basic human rights for the majority. López Obrador will also be travelling to all of the 2500 municipalities in the country, forming a grassroots organization to defend the interests of the nation. Certainly, abroad he is not popular, since the government of Calderón would be gladly giving juicy concessions to foreign companies in areas prohibited by the Constitution, such as oil. Whenever the spurious government will attempt to do something against the interests of the nation, this will be already organized and able to mobilize, forcing the spurious government to listen to the people.

The new legitimate government will be using the Republican eagle as its symbol, used by president Benito Juarez. Its goal will be to create a new Republic, restoring our country from the current state of corruption and inequality.

The national and international media do not mention all these details in their reports, so most people do not know what is going on in Mexico, even when it is a historical point. There is a huge pacific movement spreading through the country, fighting for their rights in an organized way that, at least to my knowledge, has had no precedent in any other country. What we can do to support the movement for a new Repulbic in Mexico is to spread the word. So please forward this post to anybody who might be interested.


Web 3.0 already???

What to expect from Web 3.0 by ZDNet's Phil Wainewright -- Web 2.0 is just a staging post. Web 3.0 is coming, and it's going to recreate our notion of the application as well as upsetting a few applecarts along the way.

New aphorisms

*“If we could achieve all that we wanted, there would not be anything left to enjoy”

*“It's much easier to take a woman into your bed than into your life”

*“Winning or losing does not matter as much as what you learn from it”

“For most things, you need to give in more than what you get out. (2nd law of homodynamics?)”

*“Do not suffer for what you lack,
enjoy what you have”

“Those who have less usually give more”

“If you care too much about your goals, you will never reach them.”

“Using time for yourself does not mean losing it” -Nadia

“(...) our brains are only minuscule fragments of the universe, much too small to hold all the facts of the world but not too idle to speculate about them” -Valentino Braitenberg, Vehicles, p. 1.

More Aphorisms here.

New cartoons: Complex Humour

I've added seven new cartoons to Complex Humour

More cartoons @ Complex Humour.


New Paper: Complexity and Philosophy

  • Heylighen, F., P. Cilliers, and C. Gershenson (forthcoming 2007). Complexity and Philosophy In Bogg, J. and R. Geyer (eds.) Complexity, Science and Society. Radcliffe Publishing, Oxford.

  • Abstract: The science of complexity is based on a new way of thinking that stands in sharp contrast to the philosophy underlying Newtonian science, which is based on reductionism, determinism, and objective knowledge. This paper reviews the historical development of this new world view, focusing on its philosophical foundations. Determinism was challenged by quantum mechanics and chaos theory. Systems theory replaced reductionism by a scientifically based holism. Cybernetics and postmodern social science showed that knowledge is intrinsically subjective. These developments are being integrated under the header of "complexity science". Its central paradigm is the multi-agent system. Agents are intrinsically subjective and uncertain about their environment and future, but out of their local interactions, a global organization emerges. Although different philosophers, and in particular the postmodernists, have voiced similar ideas, the paradigm of complexity still needs to be fully assimilated by philosophy. This will throw a new light on old philosophical issues such as relativism, ethics and the role of the subject.

Internet slowdown

I don't know about you, but we've had in Belgium some serious Internet slowdowns for a few weeks already. Sites such as digg, Gmail and blogger have been periodically timing out.

They seem correlated with an excessive increase in SPAM I'm receiving... about 100 a day. Spammers have evolved in such a way to generate automatically different messages with different words (so that they will be difficult to detect by text based filters), from randomly generated addresses (so that they cannot be tracked or blocked), and which have randomly generated links to sites that are simple redirectors to porn portals... Changing randomly the characteristics of these messages make it difficult for anti-spam technologies to categorize them as spam... Well, even if they do, their massive propagation through the Web slows down everybody! What could be done to stop such foul behaviour??? Moreover, which solution would not be only temporal, since spammers are constantly evolving their techniques... (e.g. about a year ago there was a wave of sending images with text to bypass text filtering...)

Or maybe everybody is running their FasterFox turbo charged???

PhD thesis in progress online

I am finally compiling my PhD thesis. Please feel free to check the latest snapshot. Any comment/suggestion/feedback would be more than welcome.

Most of the contents of the thesis are the outcome of my work on self-organizing systems.


Complex systems are difficult to design and control. There are several particular methods for coping with complexity, but there is no general methodology. In this thesis I propose such a methodology. This is based in the description of the system as self-organizing. The methodology proposes a series of steps to follow to find proper mechanisms that will promote elements to find solutions to problems by actively interacting among themselves.

A general introduction to complex thinking is given, since designing self-organizing systems requires a non-classical way of looking at things. To illustrate the methodology, I use as case studies self-organizing traffic lights, self-organizing bureaucracies, and self-organizing artifacts in an ambient intelligence scenario, along with other possible areas of application.