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)

The description of data and computer programs with the use of numbers is epistemologically valuable, because it allows to identify the limits of different types of computations. This applies in particular to discrete computations, which can be described by means of computable numbers in the Turing sense. The mathematical fact that there are real numbers of a different type, i.e. uncomputable numbers, determines the minimal limitations of digital techniques; on the other hand, however, it points to the possibility of the (...) theoretical development and physical implementation of computationally stronger techniques, such as analogue-continuous computation. The analyses presented in this article lead to the conclusion that physical implementations of unconventional computations require the occurrence of actually infinite quantities in nature. Although some arguments of theoretical physics support the physical existence of such quantities, they are not definitive. (shrink)

This article defends a modest version of the Physical Church-Turing thesis (CT). Following an established recent trend, I distinguish between what I call Mathematical CT—the thesis supported by the original arguments for CT—and Physical CT. I then distinguish between bold formulations of Physical CT, according to which any physical process—anything doable by a physical system—is computable by a Turing machine, and modest formulations, according to which any function that is computable by a physical system is computable by a Turing machine. (...) I argue that Bold Physical CT is not relevant to the epistemological concerns that motivate CT and hence not suitable as a physical analog of Mathematical CT. The correct physical analog of Mathematical CT is Modest Physical CT. I propose to explicate the notion of physical computability in terms of a usability constraint, according to which for a process to count as relevant to Physical CT, it must be usable by a finite observer to obtain the desired values of a function. Finally, I suggest that proposed counterexamples to Physical CT are still far from falsifying it because they have not been shown to satisfy the usability constraint. (shrink)

Opis danych i programów komputerowych za pomocą liczb jest epistemologicznie użyteczny, ponieważ pozwala określać granice różnego typu obliczeń. Dotyczy to w szczególności obliczeń dyskretnych, opisywalnych za pomocą liczb obliczalnych w sensie Turinga. Matematyczny fakt istnienia liczb rzeczywistych innego typu, tj. nieobliczalnych, wyznacza minimalne ograniczenia technik cyfrowych; z drugiej strony jednak, wskazuje na możliwość teoretycznego opracowania i fizycznej implementacji technik obliczeniowo silniejszych, takich jak obliczenia analogowe-ciągłe. Przedstawione w artykule analizy prowadzą do wniosku, że fizyczne implementacje obliczeń niekonwencjonalnych wymagają występowania w przyrodzie (...) wielkości nieskończonych aktualnie. Za fizycznym istnieniem takich wielkości przemawiają wprawdzie pewne argumenty fizyki teoretycznej, nie są one jednak ostateczne. (shrink)

The article analyses the role of Church’s Thesis (hereinafter CT) in the context of the development of hypercomputation research. The text begins by presenting various views on the essence of computer science and the limitations of its methods. Then CT and its importance in determining the limits of methods used by computer science is presented. Basing on the above explanations, the work goes on to characterize various proposals of hypercomputation showing their relative power in relation to the arithmetic hierarchy. The (...) general theme of the article is the analysis of mutual relations between the content of CT and the theories of hypercomputation. In the main part of the paper the arguments for abolition of CT caused by the introduction of hypercomputable methods in computer science are presented and critique of these views is presented. The role of the efficiency condition contained in the formulation of CT is stressed. The discussion ends with a summary defending the current status of Church’s thesis within the framework of philosophy and computer science as an important point of reference for determining what the notion of effective calculability really is. The considerations included in this article seem to be quite up-to-date relative to the current state of affairs in computer science.1. (shrink)