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

New Book: Complexity: 5 Questions

Image
This volume consists of short, interview-style contributions by leading figures in the field of complexity, based on five questions. The answers trace their personal experience and expose their views on the definition, aspects, problems and future of complexity. The aim of the book is to bring together the opinions of researchers with different backgrounds on the emerging study of complex systems. In this way, we will see similarities and differences, agreements and debates among the approaches of different schools. Contributors: Peter M. Allen, Philip W. Anderson, W. Brian Arthur, Yaneer Bar-Yam, Eric Bonabeau, Paul Cilliers, Jim Crutchfield, Bruce Edmonds, Nigel Gilbert, Hermann Haken, Francis Heylighen, Bernardo A. Huberman, Stuart A. Kauffman, Seth Lloyd, Gottfried Mayer-Kress, Melanie Mitchell, Edgar Morin, Mark Newman, Grégoire Nicolis, Jordan B. Pollack, Peter Schuster, Ricard V. Solé, Tamás Vicsek, Stephen Wolfram. Get it at Amazon.com Check out more books from the 5 Questions s...
Read more

Sites that revolutionized the Web

I compiled a list of the websites that have changed the way information is produced, handled, or distributed over the Internet. Many of these sites have something in common: they enable users (human or software) to judge the relevance of their content, to provide "interesting" information to others. This has been called distributed cognition or collective intelligence: like diligent ants, the small contributions of many people or sites lead to great achievements and sources of information. Google . The most effective search engine for several years now. It judges the relevance of a webpage (its PageRank) by the PageRank of webpages that link to it. Thus, if many webpages link to a certain site, this should be interesting. And even more if those webpages are interesting themselves. Google has become an empire of free web-based utilities (in some cases buying other companies): GMail . One of the most flexible free web-based mail providers , it gives users almost 3Gb of disk sp...
Read more