Κυριακή, 9 Δεκεμβρίου 2012

The Active Element Machine

The Active Element Machine is a new model of computation invented by  Michael Stephen Fiske. The model can use a random bit source from the environment to generate an arbitrary real number in the unit interval.  In addition, by using the same randomness, the machine can decide any language L ⊆ {0,1}*. In other words, this machine has capabilities that transcend the capabilities of the Turing machine.

Παρασκευή, 16 Νοεμβρίου 2012

Super-recursive algorithms

It seems that some people do not understand the connection
between hypercomputation and what Mark Burgin calls super-recursive algorithms. According to Burgin, "super-recursive algorithms are algorithms that control hypercomputation." In different words, a method that describes a task that produces a result not computable by a Turing machine is a super-recursive algorithm (or a hyperalgorithm, as I like to call them).

Τετάρτη, 14 Νοεμβρίου 2012

Will my program terminate?

Roughly speaking, Turing has proved that it is not possible to tell whether a computer program will terminate or not. Recently, William Gasarch posted an article to the arXiv in which he shows how one can prove program termination. Gasarch does not disprove Turing, but " discuss various ways to prove that [a] program terminates".

Παρασκευή, 26 Οκτωβρίου 2012

Κυριακή, 21 Οκτωβρίου 2012

Yet another proof?

Today I discovered yet another proof of the Church-Turing thesis (CTT)! In particular, Ramón Casares in his Proof of Church's Thesis proves the CTT using another more "general" thesis:
Persons’ syntax engine is a Finite Universal Turing Machine.
 A finite Turing machine is one that has a tape of finite length. Any person has a syntactical capability, that is the ability to speak a language and a syntax engine is a machine with a syntactical capability. So the question is whether there are machines that can really understand languages? Obviously, it is one think to dully manipulate symbols and another to understand the meaning associated to symbols. After all, this was nicely demonstrated with the Chinese Room Argument (in essence, this argument is a "proof" that intelligence cannot be equated with symbol manipulation, and, obviously, it is not an argument "against the possibility of true artificial intelligence"). Now the problem with this proof is that it relies on another thesis, whose validity has not been proved, although, according to Casares, it is so obvious that it holds true! 

Κυριακή, 14 Οκτωβρίου 2012

An interesting event

honoring István Németi's 70th birthday took place in Budapest, last September. The theme of the conference was the connection between logic and relativity theory. Obviously, since Németi initiated what is now called relativistic computing, a number of speakers presented work that falls in this research area. Unfortunately, for a number of good reasons, it was not possible to attend the event, so I cannot give a report of it. Nevertheless, when skimming through the web pages, one can easily see that the event was very interesting. I just hope more events like this will take place.

Τετάρτη, 1 Αυγούστου 2012

Finally it has been proven!

I had the impression that the Church-Turing thesis has not been proven, but a recent posting to the Arxiv server claimed otherwise. In partricular, Nachum Dershowitz and Evgenia Falkovic in their extended abstract entitled "A Formalization and Proof of the Extended Church-Turing Thesis" claim that they offer a proof of the Extended Church-Turing Thesis: Every effective algorithm can be efficiently simulated by a Turing machine. Interestingly, this proof uses the notion of classical algorithm which is a time-sequential state-transition system, whose transitions are partial functions on its states. But obviously, this is not an algorithm but something that someone calls a classical algorithm. Now if one has a deep desire to prove the Church-Turing thesis, then she can formulate and prove it inside Eff, that is, the effective topos (see Categorical Logic and Type Theory, p. 402)! In a nutshell, no I don't think this paper is a proof of the CTT.

Τρίτη, 31 Ιουλίου 2012

A computable universe?

Today I received an e-mail notification about a new book entitled A Computable Universe: Understanding and Exploring Nature as Computation. According to the publisher, the book It focuses on two main questions:
  • What is computation?
  • How does nature compute?
Obviously there is an oxymoron here—if one does not know what  computation is, then it makes absolutely no sense to say anything about nature's computational capabilities! Notwithstanding, I find extremely naive the idea of a computable universe. To me it is more science fiction than science. But I have argued against this absurd idea elsewhere, so I will say no more here.

PS The book's site states that "contributors are world-renowned experts", in what respect is the editor a world-renowned expert?

Σάββατο, 26 Μαΐου 2012

Interactive Recurrent Neural Networks

Recently, Jérémie Cabessa and Hava T. Siegelmann published a paper entitled The Computational Power of Interactive Recurrent Neural Networks. In this paper, the authors discuss a new form of interactive recurrent neural networks that are able to interact with other systems and/or the environment. These neural networks are shown to be strictly more powerful than interactive Turing machines, which implies that they have hypercomputational capabilities.

Τρίτη, 10 Απριλίου 2012

Hypercomputation and Special Relativity

In a recent paper entitled Existence of Faster Than Light Signals Implies Hypercomputation Already in Special Relativity, which was posted to ArXiv, it is discussed whether it is possible to hypercompute in an ordinary spacetime. The authors conclude that this is possible provided that there are elementary particles that can travel faster than the light. Whether this is possible is another problem. Nevertheless, let me say that in a recent paper entitled Measurement of the neutrino velocity with the OPERA detector in the CNGS beam it is argued that neutrinos can travel faster than the light.

PS It was shown that neutrinos do not travel faster than light.

Τετάρτη, 28 Μαρτίου 2012

A rebuttal to a review

In May, 2009 a review of my book on hypercomputation appeared in the Computing Reviews. Although I submitted a rebuttal to the review, it appeared slightly edited. So for reasons of completeness, I post my complete rebuttal here today.

-->
It is known that disagreements in the academic world are quite common and constitute the essence of any scientific production. Everybody who is doing some scholar work is virtually exposed to criticism. Nevertheless, it is one thing to criticize one's work and another to present a piece of work in such a way that potential readers get the impression that the work is almost worthless! A typical example of this “reviewing technique” is to assert that an author fully and unconditionally subscribes to a particular idea, when, in fact, she/he explicitly states that one cannot be sure about the idea!

Apparently, Zenil's review is based on this “technique” and has almost fiercely tried to convince his readers that I practically have no idea what I am talking about! For example, he argues that I subscribe to the Lucas-Penrose argument (LPA) without saying that the book includes many counter-arguments to the LPA. Interestingly, Zenil states that I use Searle's ideas to “immediately acknowledge hypercomputation” (ergo, I believe in the validity of Searle's ideas) and at the same time he states that I do subscribe to the LPA, when it is known that Searle rejects the LPA! Unfortunately, this “technique” is employed in other parts of the review. In particular, when he talks about the space-time granularity, Zenil argues that “the author assumes that space and time are continuous--in spite of quantum mechanics.” First of all Schrödinger's equation assumes a continuous space and time so the non-granularity of space and time is self-evident. Nevertheless, in my work I was careful enough not to employ such seemingly knock-out arguments and so I have explicitly stated (on page 147) that “it is clear that for the time being, nobody really knows the truth regarding spacetime granularity.” In different words, although I do believe that space and time are continuous, still there is no scientific proof for this.

Another quite problematic part of Zenil's review is statements like the following:

as it is acknowledged in the book itself, several models are missing and those included are only introductions. Consequently, the book is more a dictionary of models of hypercomputation that Syropoulos chose to include.”

Firstly, I would be really grateful to anybody who could bring to my attention serious models/proposals of hypercomputation. Of course any model/proposal that was suggested after the book was published, can be included in a future edition of the book. Secondly, I admit that in a couple of case I did not discuss some older ideas just because more recent ones describe systems based on the same principles in a more scientific and rigorous way. Thirdly, there is no discussion of hypermachines based on ideas that are very controversial.

It is true that I find it extremely naïve to believe to a Turing computable view of the mind/universe. However, when I try to summarize computationalism by saying that we are tiny Turing machines [that live in a “Turing-verse”!], I actually mean that our capabilities in thinking the very notion of computation are actually delimited by the capabilities of the Turing machine. In other words, we cannot compute more than a Turing machine (do not forget that computationalists believe that even feelings are computations). So, I have used this expression as a metaphor, that is, a figure of speech. Consequently, I did not expect (educated) readers to conclude that I think that anyone who subscribes to computationalism believes that people are literally Turing machines.

It is clear that computation has played, plays, and will play a very important role in our societies (we already live in an Information Society); but so does Newtonian mechanics as well, which, nevertheless, is not universally valid. Under the light of the Newtonian mechanics paradigm, let me state that I personally believe that hypercomputation is, in a certain sense, to classical computability theory what the theory of relativity is to classical mechanics.

Unfortunately, Zenil writes without asking himself if his interpretation is the only possible. For instance, he argues in the sequel that “there is no evidence that the [Church-Turing] thesis may be wrong, but a lot of evidence that it is correct.” This is true, however, at the same time there is so much evidence that space and time are continuous, but still Zenil does not accept the validity of this hypothesis! Also, let me remind that evidence is not enough; in science we need proofs. And that is why the Church-Turing thesis (CTT) stands as a hypothesis. Obviously, only when (and if) the CTT will be proved beyond any doubt to be valid, only then hypercomputation will have no place to stand!

In addition, I do not think that the section of the CTT has errors—since I do not believe in the validity of this thesis, I presented a number of different formulations without going into the details. We know that the thesis was originally formulated in 1935 when the only “models” of computation were the λ-calculus and general recursive functions; so we cannot speak about a thesis which is the result of “the convergence of the definitions of computation.”
Another serious mistake of Zenil's is to accuse me that I believe that “a hypercomputer is more feasible than a quantum computer.” I thank him for giving me issues to understand me differently and better! But even a simple reader of the book, I mean, even a reader who does not pretend to be a scholar, can quickly verify that (on page 10) I state that “I am convinced that future advances in technology will allow us sooner or later to build computers based on these paradigms,” where “these paradigms” refers to quantum computing, etc. Last, but certainly not least, the first chapter of the book concludes as follows:

The truth is always in the middle, and I agree fully with Christof Teuscher and Moshe Sipper [200] when they say: "So, hype or computation? At this juncture, it seems the jury is still out—but the trial promises to be riveting."

At this point I stop. What hurts me is not the critique. Perhaps even nor the interpretative injustice, nor the critical unfairness of Zenil (anyway, we cannot constraint the reading strategy of a reader, and nobody can understand more than she/he can: by reading, the reader re-writes what she/he reads). But I am sad to encounter one more time the transmutation of the critique into a means or an opportunity of getting authority.

Πέμπτη, 9 Φεβρουαρίου 2012

Turing's Thesis and a More General Physical Principle

Recently, Matthew P. Szudzik posted an article to the arXiv
 server that is entitled "Is Turing's Thesis the Consequence of a More General Physical Principle?" Szudzik ivnestigates Robert Rosen’s hypotheses, which were put forth in "Church’s thesis and its relation to the concept of realizability in biology and physics". Roughly, one can say that these hypotheses state that the universe is discrete, deterministic, and computable.  A direct consequence of these hypotheses is the Church-Turing Thesis. Szudzik recognizes that these hypptheses are not correct and, thus, one needs to reformulate them:
This sort of reformulation was first attempted by Konrad Zuse [18, 19] in the 1960’s. Since then, increasingly sophisticated attempts have been made by Edward Fredkin [3] and Stephen Wolfram [17]. In contrast, Roger Penrose [9, 10] has speculated that the universe might not be computable, but efforts to find experimental evidence for this assertion have not succeeded.

Unfortunately, Szudzik ignores a number of papers that clearly demonstrate that there non-computable phenomena in the universe. In addition, he has failed to put hypercomputation in the picture. One could easily say that there are phenomena that are not computable but which are clearly hypercomputable. Nevertheless, a major problem with Szudzik's approach is that he assumes that we  have deep understanding of the laws of the universe, when in fact we know next to nothing!  

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