Παρασκευή, 13 Δεκεμβρίου 2013

On the Computing Spacetime

Fotini Markopoulou has published a paper entitled The Computing Spacetime. The first sentence of this paper is: That the Universe can be thought of as a giant computation is a straightforward corollary of the existence of a universal Turing machine. This is a very bold statement, to say the least. We have absolutely no idea what are the (ultimate) laws of the universe and yet we can immediately prove that it is a gigantic computer! Now let's see the proof:
The laws of physics allow for a machine, the universal Turing machine, such that its possible motions correspond to all possible motions of all possible physical objects. That is, a universal quantum computer can simulate every physical entity and its behavior. This means that physics, the study of all possible physical systems, is isomorphic to the study of all programs that could run on a universal quantum computer. We can think of our universe as software running on a universal computer.
First let me remark that Markopoulou confuses universal Turing machines with universal quantum computers, which means, I suppose, that she assumes that the Church-Turing thesis is valid. Second, it is known that the Turing machine operates in a Newtonian universe and naturally does not take under consideration any quantum phenomena. Third, to say that physics is essentially equivalent to the study of quantum programming is a fallacy because we have no idea what are the ultimate laws of universe. Unless, of course, we assume that fairytale physics is real physics. In this case, it is crystal clear that we are talking nonsense.

As with fairytale physics, the problem with the the-Universe-is-a-computer paradigm is that there is no experimental evidence that actually the universe computes something. In fact, I am pretty sure that this is something like an Illuminati conspiracy theory rather than a real scientific theory. Naturally, please bear on mind that the problem of quantifying gravity has not been solved yet.

PS Today (20/02/2014) I discovered a preprint entitled  The Universe is not a Computer. In this paper the author puts forth an interesting argument against the validity of the idea that the universe is a computer.

Τρίτη, 10 Δεκεμβρίου 2013

Fairytale Physics

Jim Baggot in his recent book that is entitled Farewell to Reality: How Fairytale Physics Betrays the Search for Scientific Truth  advocates the idea that modern physics is going in the wrong direction. In particular, he critically examines superstring theory and concludes that this theory cannot explain the existence of many things we know they exist! Similar ideas have been presented in Peter Woit's Not Even Wrong: The Failure of String Theory and the Continuing Challenge to Unify the Laws of Physics. Recently, the British newspaper The Guardian has published as debate between Baggot and string theorist Mike Duff. The later replied to Baggot's remark that "the positron was discovered in cosmic ray experiments just a couple of years after Dirac had agreed that this was what his theory predicted" as follows:
Dirac did not assume the positron; he discovered it to be a consequence of an equation that described the well-established electron. Similarly, string theorists did not assume supersymmetry, extra dimensions, the dualities of M-theory or the myriad possible universes; they discovered them to be consequences of a theory that subsumes empirically well-established features such as general relativity, gauge field theory and chiral quarks and leptons. Current research is devoted to finding out what else M-theory requires.
 The problem with Duff's argument is that none of the things superstring theory has been speculating about have been discovered! In fact, there are not even indirect evidence that might one lead to the conclusion that these bizarre things exist. (They do exist in Fringe's universe…)

One may wonder what all these have to do with computation. The answer, of course, is quite simple: when one proposes a bizarre model of computation she must make sure that the physics involved is valid beyond any doubt!

PS On the 20th episode of season 7 of The Big Bang Theory, Sheldon wonders: "Am I wasting my life on a theory that can never be proven?"  and decides to stop his work on string theory... (I read about this in the Not Even Wrong blog).

Κυριακή, 10 Νοεμβρίου 2013

On Computation

In an old entry of this blog, I had criticised a blog post who was a review of my book. The author of that review posted a new post entitled Deflating Hypercomputation, where he advertizes his paper The Physical Church–Turing Thesis: Modest or Bold? This paper is a defense of a "modest version of the Physical Church-Turing thesis":
Any function that is physically computable is  Turing computable.
The next question is, of course, what is meant by physical computable? Gualtiero Piccinini, that is, the author of this paper, proposes that "if a physical process is a computation, it can be used by a finite observer to obtain the desired values of a function". Now, finite observers are "human beings and any other intelligent beings of similarly bounded capacities". In an explanation of this description, he includes among observers beings that are located in spacetimes that are (currently?) inaccessible to humans (so hypercomputation near a black hole is not a fantasy!).  Physical processes must be executable, automatic, uniform, and reliable in order to be usable. In particular,
  • executable means that the process can be started by the observer to generate results;
  • automatic means that the process is mechanical;
  • uniform means that the process is the same for different inputs; and
  • reliable means that it generates correct results in the course of execution.
Then he proposes some other sub-criteria that should be used to define the notion of physical process. However, this definition is surprisingly similar to the definition of an algorithm that follows and which is borrowed from Fundamentals of data structures in PASCAL:
Definition An algorithm is a finite set of instructions that if followed, accomplish a particular task. In addition, every algorithm must satisfy the following criteria:
  1. input: there are zero or more quantities that are externally supplied;
  2. output: at least one quantity is produced;
  3. definiteness: each instruction must be clear and unambiguous;
  4. finiteness: if we trace out the instructions of an algorithm, then for all cases the algorithm will terminate after a finite number of steps;
  5. effectiveness: every instruction must be sufficiently basic that it can in principle be carried out by a person using only pencil and paper. It is not enough that each operation be defined, but it must also be feasible.
In different words, he is not proposing something entirely new.  Now in my book I had used the following definition of computation, which I have borrowed from Computation is just interpretable symbol manipulation; cognition isn't:
Definition Computation is an implementation-independent, systematically interpretable, symbol manipulation process.
Obviously, this definition is far more general and it can be applied in cases where Piccinini's formulation fails. Also, I have used this definition to rule out "computing" walls and stones as genuine computing devices. In conclusion, Piccinini "response" shows that he did not actually read the book. 

Πέμπτη, 4 Ιουλίου 2013

Infinite computations with random oracles

Merlin Carl and Philipp Schlicht have posted an article to the arXiv entitled infinite computations with random oracles. A basic result of classical computability theory states that if a real x is Turing-computable relative to all oracles in a set of positive measure, then this real number is Turing-computable in the empty oracle. In different words,  the use of random generators does not enrich the set of computable functions. The authors examine whether this is true for models of infinite computation. In particular, for Infinite Time Turing Machine, Infinite Time Register machines, α-Turing machines, and ordinal Turing/register machines, the authors ask whether there are noncomputable reals (in the sense of the machine type) that are reducible to all oracles in a set of positive measure. The authors show that the answer is negative for most models of infinite computation.

Κυριακή, 16 Ιουνίου 2013

Quantum Computing and… Democritus

Yesterday I noticed that there is a new book entitled Quantum Computing since Democritus. I haven't read the book but from what I have seen, it seems that it is a presentation of the field of quantum computing in a colloquial language (Democritus is called a dude!). What is really interesting is one of the reviews posted at amazon's web page. The review is by some one called Guy Wilson but it seems that Guy Wilson is actually Joy Christian. Christian does not really believe that it will possible to build scalable quantum computers.

First of all, it is true that one cannot go to a computer shop and buy a quantum computer today, but this does not mean that there are no quantum computers. For example, Google bought a quantum computer recently. But Christian argues that he has disproved Bell's theorem, which, roughly speaking, implies that it is not possible to build scalable quantum computers.

Unfortunately, in a way the situation looks familiar–just because someone has built a career on something, it doesn't mean quantum computing, or hypercomputation for that matter, is nonsense! And this is something the author of the book should not forget!

PS Frankly, I don't understand what's the connection between quantum computing and Democritus, but then again I haven't read the book…

Τρίτη, 7 Μαΐου 2013

Creating a Mind

Recently, I read a review by Colin McGinn of Ray Kurzweil's How to Create a Mind: The Secret of Human Thought Revealed. According to McGinn, the book reveals, at last, the secret of human thought which is pattern recognition! Kurzweil argues that one needs to build a machine that recognizes patterns in order to create a mind. Personally, I find this idea extremely naive because pattern recognition is just one of mind's many functions. On the other side, McGinn says that "the brain is causally connected to the mind and the mind contains and processes information", which seems bizarre. I always thought that the brain induces the mind but this statement implies that the brain and the mind are two separate entities. What is even more bizarre are reviews of the book like this:

Ray Kurzweil's understanding of the brain and artificial intelligence will dramatically impact every aspect of our lives, every industry on Earth, and how we think about our future. If you care about any of these, read this book!
So we are living in a new era where  Kurzweil's theory will change our life. Are we serious? Scanners are going to profoundly change our life? One reader posted the following to amazon's site:
In "How To Create a Mind," Ray Kurzweil offers a fascinating and readable overview of his theory of how the human brain works, as well as a road map for the future of artificial intelligence.
Really? Well, sometimes I wonder whether some people are getting paid to say such bullshit! All in all, I fully agree with McGinn's review and yes I do not believe there will be dramatic changes in our life because of  Kurzweil's theory.

PS In June 2012, the International Journal of Machine Consciousness published a special issue (Volume 04, Issue 01) on mind uploading. Currently, the contents of the issue are freely available.

Κυριακή, 5 Μαΐου 2013

Oracle Machines and the Verification Problem

Florent Franchette presented an interesting problem in his "Oracle Hypermachines Faced with the Verification Problem". Franchette argues that a physical oracle machine cannot be used to prove that physical hypercomputers exist simply because we cannot verify the results computed by the machine. However, an answer to what can be computed by a form of oracle Turing machine is described in "Computational complexity with experiments as oracles" (see also "Computational complexity with experiments as oracles. II. Upper bounds"). Roughly, their oracle machine, which is called an analog-digital Turing machine, is an ordinary Turing machine coupled to an abstract physical experiment. The authors of these papers prove that this machines have computational power that goes beyond the Church-Turing barrier. Now, if one proves that a machine is actually a hypercomputer, then I think there is no need to verify results computed. After all, we trust the results computed by ordinary machines, so why shouldn't we  trust the results computed by a hypercomputer?

Κυριακή, 14 Απριλίου 2013

Τρίτη, 12 Μαρτίου 2013

There is nothing wrong with particles that travel faster than the light!

Judit  Madarász and Gergely Székely, in a paper that was recently posted to the arXiv and which is entitled The Existence of Superluminal Particles is Consistent with Relativistic Dynamics, examine whether particles that are supposed to travel faster than the light violate any physical law. Their conclusion is that the existence of particles that travel faster than the light cannot be ruled out by special relativity.
 

Σάββατο, 19 Ιανουαρίου 2013

Non-Universality in Computation

Selim Akl has convincingly argued that there is no universal computer. This may come to a surprise to people since one of the first things we learn when studying computability theory is the notion of the universal Turing machine. But then again, we learn that there is a thesis that dictates what and what cannot be computed!

A "Solution" to Riemann Hypothesis

Riemann hypothesi s is "is a conjecture that the Riemann zeta function has its zeros only at the negative even integers and complex n...