Παρασκευή, 26 Δεκεμβρίου 2008

"How to Program an Infinite Abacus"

Joachim Lambek wrote an interesting paper entitled "How to Program an Infinite Abacus" which was published in the Canadian Mathematical Bulletin. Unfortunately, this paper is currently not available in any form. For the benefit of all those people who might like to have a look at this paper, I have prepared a transcription of this paper which is available here.

Δευτέρα, 1 Δεκεμβρίου 2008

A comment on a comment

Recently, "someone" posted a review of my book on hypercomputation on the Brains site. The reviewer argues that

This area is full of problems, some of which are physico/mathematical and some of which are conceptual. Unfortunately, from a quick sample, Syropolous's book does not avoid common mistakes and confusions—some of which I've been trying to correct in my own work.

First of all, I have to admit that back in 2004 I read a paper by this reviewer, but at that time I did not considered it interesting. However, after I read this review of my book, I read The Physical Church-Turing Thesis: Modest or Bold?, the reviewer's latest manuscript, in order to see what he meant by common mistakes and confusions and how he was trying to solve them. In this manuscript, the reviewer puts forth a number of criteria that every machine has to satisfy in order to be ``useful for physical computing.'' These criteria are:

  • Readable Inputs and Outputs
  • Process-Independent Rule
  • Repeatability
  • Resettability
  • Physical Constructability
  • Reliability
Obviously these criteria constitute a description of a feasible computing device. Unfortunately, it is obvious that these criteria are too restrictive or, to put it in another way, these criteria assume that only "modern" computers are useful physical computing devices. In particular, what for one person is readable for someone else is not readable at all (e.g., data on a computer screen are not readable by a blind person). As far it regards physical constructability, the reviewer talks about Malament-Hogarth spacetime computers and tries to prove that they are non-feasible while he ignores two important papers in the field: Non-Turing Computations Via Malament–Hogarth Space-Times and Relativistic computers and the Turing barrier.

All in all, I fail to see how he can correct the problems with such views. In addition, his view is deeply mechanistic and unfortunately too simplistic.

Κυριακή, 2 Νοεμβρίου 2008

Hypercomputation and Physical Reality

Konstantine Arkoudas argues in "Computation, hypercomputation, and physical science" why in his opinion
[T]he idea that physical science will be able to discover fundamental
computability limits is untenable.

A computation is carried out by concrete computational devices whose operation and capabilities are delimited by the laws of physics. It is one thing to argue that we have no idea what are the limits of computation and another to simple say that the limits of computation have nothing to do with physical reality. On the other hand, it is more than sure that there is a limit to what we can achieve with computing devices, but for the time being we simply do not know this limit. And this is exactly the essence of hypercomputation.

Τετάρτη, 1 Οκτωβρίου 2008

Landau levels and Riemann zeros

German Sierra and Paul K. Townsend have recently presented an idea that may lead to the solution of the Riemann hypothesis. The Riemann hypothesis is a co-recursively enumerable problem (roughly, there is an algorithm that, when given an input number, eventually halts if and only if the input satisfies the problem, but no algorithm can decide if an arbitrary input satisfies the problem or not). The solution of this and other similar problems would falsify Church's Thesis. Interestingly, Fermat's last theorem and Poincaré's conjecture are co-recursively enumerable problems, nonetheless, these problems have been decided! A proof that Church's thesis is false...?

Τρίτη, 23 Σεπτεμβρίου 2008

Hypercomputation Book

I am really happy to announce that my book on Hypercomputation has been published by Springer. Hypercomputation is a new discipline that emerged from the ascertainment that the Church-Turing Thesis (CTT) cannot be possible true. Roughly, the CTT is about what can be computed with any real or conceptual computing device. In particular, if some function is computable, then it is definitely computable by a Turing mchine, that is, Turing's archetypal conceptual computing device. Hypercomputation, asserts that functions and numbers that cannot be computed by a Turing machine, can be computed by other more powerful computing devices. The description of such machines and their computational power is the subject of this book. In particular, the book describes the various approaches to hypercomputation in nine chapters
  • Introduction
  • On the Church–Turing Thesis
  • Early Hypercomputers
  • Infinite-Time Turing Machines
  • Interactive Computing
  • Hyperminds
  • Computing Real Numbers
  • Relativistic and Quantum Hypercomputation
  • Natural Computation and Hypercomputation
There are also three appendices that briefly describe some important issues:
  • The P = NP Hypothesis
  • Intractability and Hypercomputation
  • Socioeconomic Implications

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