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...)

Comments

Post a Comment

Popular posts from this blog

The Past, Present and Future of Cybernetics and Systems Research

Summary of "The Past, Present and Future of Cybernetics and Systems Research" Symposium M at  European Meetings on Cybernetics and Systems Research (EMCSR), Vienna, Austria, April 12, 2012. Organizer: Carlos Gershenson This guided reflection on the challenges and opportunities of cybernetics and systems research (CSR) included initial interventions by panelists Peter Erdi, Helena Knyazeva, Stefan Thurner, Peter Csermely, and Alexander Lazlo. Afterwards, the floor was opened to interventions from the general public and further interventions by panelists. Commentaries were made from a broad variety of perspectives, but several general ideas can be distilled from the discussion. CSR have strongly influenced all scientific disciplines. As an example, the term "system" is used commonly in daily language. One of the breakthroughs of CSR lies in the search of commonalities across disciplines. Even when this was achieved to a certain degree, there is still a lack of
Read more

flocking memes...

Some ideas just came up, after a talk I had with Klaas , who is making a PhD on memetics... In cultural transmission of fads and so on, I've heard that there are models in which the majority imitates an elite, and the elite tries to go away from the crowd, and that gives you the dynamics... The idea is that maybe another way of looking at this phenomenon is to take the analogy of flocking: birds try to keep together (safety, direction, whatever reason), but also keep average distance to their neighbours (not to crash). If we take this mechanism into the memetic space, people will imitate many aspects surrounding them, just because of mirron neurons and the evolutionary advantage of imitation. But the separation is also important, for people assert their individuality with it... This could be seen as taking the inverse of a meme... starting to sounds like dialectics... (who would have thought that Hegel and starlings had lots in common...) Of course in the social context there are m
Read more

PhD thesis: "final" version online

After making several minor corrections, I have a "final" version of my thesis, which you can download here . I should defend it privately on April 20th, and if everything goes well, the public defense would be on May 2nd. Everybody's welcome! Design and Control of Self-organizing Systems PhD Dissertation presented by Carlos Gershenson Promoters: Prof. Dr. Bart D’Hooghe and Prof. Dr. Francis Heylighen Advisors: Prof. Dr. Bruce Edmonds Prof. Dr. Bernard Manderick Prof. Dr. Peter McBurney Prof. Dr. Ann Nowé Abstract Complex systems are usually difficult to design and control. There are several particular methods for coping with complexity, but there is no general approach to build complex systems. In this thesis I propose a methodology to aid engineers in the design and control of complex systems. This is based on the description of systems as self-organizing . Starting from the agent metaphor, the methodology proposes a conceptual framework and a se
Read more