Hypercomputation—the hypothesis that Turing-incomputable objects can be computed through infinitary means—is ineffective, as the unsolvability of the halting problem for Turing machines depends just on the absence of a definite value for some paradoxical construction; nature and quantity of computing resources are immaterial. The assumption that the halting problem is solved by oracles of higher Turing degree amounts just to postulation; infinite-time oracles are not actually solving paradoxes, but simply assigning them conventional values. Special values for non-terminating processes are likewise (...) irrelevant, since diagonalization can cover any amount of value assignments. This should not be construed as a restriction of computing power: Turing’s uncomputability is not a ‘barrier’ to be broken, but simply an effect of the expressive power of consistent programming systems. (shrink)

I discuss the philosophical implications that the rising new science of quantum computing may have on the philosophy of computer science. While quantum algorithms leave the notion of Turing-Computability intact, they may re-describe the abstract space of computational complexity theory hence militate against the autonomous character of some of the concepts and categories of computer science.

What are the limits of physical computation? In his ‘Church’s Thesis and Principles for Mechanisms’, Turing’s student Robin Gandy proved that any machine satisfying four idealised physical ‘principles’ is equivalent to some Turing machine. Gandy’s four principles in effect define a class of computing machines (‘Gandy machines’). Our question is: What is the relationship of this class to the class of all (ideal) physical computing machines? Gandy himself suggests that the relationship is identity. We do not share this view. We (...) will point to interesting examples of (ideal) physical machines that fall outside the class of Gandy machines and compute functions that are not Turing-machine computable. (shrink)

Artificial intelligence algorithms, fueled by continuous technological development and increased computing power, have proven effective across a variety of tasks. Concurrently, quantum computers have shown promise in solving problems beyond the reach of classical computers. These advancements have contributed to a misconception that quantum computers enable hypercomputation, sparking speculation about quantum supremacy leading to an intelligence explosion and the creation of superintelligent agents. We challenge this notion, arguing that current evidence does not support the idea that quantum technologies enable hypercomputation. (...) Fundamental limitations on information storage within finite spaces and the accessibility of information from quantum states constrain quantum computers from surpassing the Turing computing barrier. While quantum technologies may offer exponential speed-ups in specific computing cases, there is insufficient evidence to suggest that focusing solely on quantum-related problems will lead to technological singularity and the emergence of superintelligence. Subsequently, there is no premise suggesting that general intelligence depends on quantum effects or that accelerating existing algorithms through quantum means will replicate true intelligence. We propose that if superintelligence is to be achieved, it will not be solely through quantum technologies. Instead, the attainment of superintelligence remains a conceptual challenge that humanity has yet to overcome, with quantum technologies showing no clear path toward its resolution. (shrink)

For infinite machines that are free from the classical Thomson’s lamp paradox, we show that they are not free from its inverted-in-time version. We provide a program for infinite machines and an infinite mechanism that demonstrate this paradox. While their finite analogs work predictably, the program and the infinite mechanism demonstrate an undefined behavior. As in the case of infinite Davies machines :671–682, 2001), our examples are free from infinite masses, infinite velocities, infinite forces, etc. Only infinite divisibility of space (...) and time is assumed. Thus, the infinite devices considered are possible in a Newtonian Universe and they do not conflict with Newtonian mechanics. Note that the classical Thomson’s lamp paradox leads to infinite velocities which may not be producible in acceptable models of Newtonian mechanics. Finally, it is shown that the “paradox of predictability” is similar to the inverted Thomson’s lamp paradox. (shrink)