Αναρτήσεις

Προβολή αναρτήσεων από 2020

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.