Αναρτήσεις

On the Limits of Computation

 Recently I wrote an article on the The Limits of Computation , which was published in Philosophy Now . In this article I argue in favor of the idea that the limits of computation are currently unknown. In addition, I explore how this idea affects our understanding in a number of areas.

Using an electronic amoeba to quickly find an approximate solution to traveling salesman problem

The traveling salesman problem is about a salesman that has to start from a specific town and after visiting a number of towns only once, he/she has to return to the starting town. The real problem is to minimize the total length of the trip. It has been shown that this problem is NP-complete, which practically means that this is a very difficult problem to solve with a computer. However, Kenta Saito, Masashi Aono, and Seiya Kasai from Japan have shown that an electronic amoeba can give an approximate solution to this problem in linear time. Practically, this means that the new approach can transform a difficult problem to an easy one. The Japanese researchers reported their findings in a paper in scientific reports .

New milestone in quantum supremacy

A new kind of quantum computer that harnesses photons has achieved a new breakthrough in quantum supremacy. In particular, this machine completed a computational task in 200 seconds while an ordinary supercomputer would require 2.5 billion years. The computer employes a technique called Gaussian boson sampling (a photon is a boson) and a complete description of the machine is given in an article published in Sciece (everyone can read it for free).

New and Notable Books

Recently Lee Yiwata sent me a list of book related to hypercomputation. The list is rather complete but I would like to mention only the most recent titles that I did not happen to skim through. Biological Hypercomputation and Degrees of Freedom by Carlos Eduardo Maldonad. Interactive Computation: The New Paradigm edited by Dina Goldin, Scott A. Smolka, and Peter Wegner.  Ordinal Computability: An Introduction to Infinitary Machines by Merlin Carl. Computation and its Limits by Paul Cockshott, Lewis M Mackenzie, and Gregory Michaelson. Computational Matter edited by Susan Stepney, Steen Rasmussen, and Martyn Amos. Physical Computation: A Mechanistic Account by Gualtiero Piccinini. Church’s Thesis. Logic, Mind and Nature edited by Adam Olszewski, Bartosz Brożek, Piotr Urbańczyk. The books Computation and its Limits and Physical Computation: A Mechanistic Account are not in favor of hypercomputation, nevertheless, they might be of interest to some people. Personally, I am not re

Turing Machine Simulation

 Hypercomputation is about machines that transcend the computational power of the Turing machine. However, I think it is quite instructive to really understand the power of the Turing machine. Therefore, I think play with a Turing machine simulator is quite instructive. The Turing machine simulator by Martín Ugarte is a very interesting and powerful simulator that I recommend to everyone who wants to play with Turing machines.

The Rolf Nevanlinna Prize

A few days ago I read that Constantinos Daskalakis got the Rolf Nevanlinna Prize for  For transforming our understanding of the computational complexity of fundamental problems in markets, auctions, equilibria, and other economic structures. His work provides both efficient algorithms and limits on what can be performed efficiently in these domains. Thus, according to this, we now can somehow compute economies. However, even economists have started to realize that economies cannot be described with  mathematics only. In fact,  Why economists need to expand their knowledge to include the humanities is a recent article that discusses exactly this problem. Daskalakis's approach is based on the assumption that humans are Turing machines. Unfortunately, they are not and this is the reason why economists fail so miserably in their predictions. Furthermore, there are some other things that people who work in computational economics "fail" to realize. For example, ev