On different meanings of analogicity in computer science

Authors

  • Paweł Stacewicz

DOI:

https://doi.org/10.15633/ss.2486

Keywords:

continuous computations, analog computations, analogicity, GPAC model, Turing machine, natural computing, hypercomputations, computability

Abstract

Two different types of analog computations are discussed in the paper: 1)
analog-continuous computations (performed physically upon continuous signals),
2) analog-analogical computations (performed naturally by means of so
called natural analogons of mathematical operations). They are analyzed with
regard to such questions like: a) are continuous computations physically implementable?
b) what is the actual computational power of different analog
techniques? c) can natural (empirical) computations be such reliable as digital?
d) is it possible to develop universal analog computers (assuming that they
should be functionally similar to universal Turing machine)? Presented analyses
are rather methodological than formal.

References

Blum L., Shub M., Smale S., On a Theory of Computation and Complexity over

the Real Numbers: NP-completeness, Recursive Functions and Universal Machines,

„Bulletin of the American Mathematical Society” 21 (1989), s. 1–46.

Chaitin G., The Limits of Mathematics, London 2003.

Costa J. F., Graça D., Analog Computers and Recursive Functions over the

Reals, „Journal of Complexity” 19 (2003) iss. 5, s. 644–664.

Deutsch D., Quantum Theory, the Church-Turing Principle and the Universal

Quantum Computer, „Proceedings of the Royal Society of London” 400

(1985) iss. 1818, s. 97–117.

Fichtenholz G. M., Rachunek różniczkowy i całkowy, t. 2, tłum. R. Bittner,

B. Gleichgewicht, T. Huskowski, Warszawa 1997.

Handbook of Natural Computing, ed. G. Rozenberg, T. Back, J. N. Kok, Berlin–

Heidelberg 2012.

Harel D., Rzecz o istocie informatyki. Algorytmika, tłum. Z. Weiss, P. Carlson,

Warszawa 2000.

Ifrah G., Historia powszechna cyfr, t. 2, tłum. K. Marczewska, K. Szeżyńska-

-Maćkowiak, Warszawa 2006.

O różnych sposobach rozumienia analogowości w informatyce 115

Kari L., Rozenberg G., The Many Facets of Natural Computing, „Communications

of the ACM” 51 (2008) iss. 10, s. 72–83.

Krajewski W., Prawa nauki. Przegląd zagadnień metodologicznych i filozoficznych,

Warszawa 1998.

Kulka Z., Nadachowski M., Wzmacniacze operacyjne i ich zastosowanie, cz. 2,

Warszawa 1982.

Marciszewski W., Racjonalistyczny optymizm poznawczy w Gödlowskiej wizji

dynamiki wiedzy, w: Przewodnik po epistemologii, red. R. Ziemińska,

Kraków 2013.

Moore C., Recursion Theory on the Reals and Continuous-Time Computation,

„Theoretical Computer Science” 162 (1996) iss. 1, s. 23–44.

Mycka J., Obliczenia dyskretne i ciągłe jako realizacje antropomorficznej i fizycznej

koncepcji efektywnej obliczalności, w: Światy matematyki. Tworzenie

czy odkrywanie, red. I. Bondecka-Krzykowska, J. Pogonowski, Poznań 2010.

Mycka J., Piekarz M., Przegląd zagadnień obliczalności analogowej, w: Algorytmy,

metody i programy naukowe, red. S. Grzegórski, M. Miłosz, P. Muryjas,

Lublin 2004.

Polak P., Od informatyki empirycznej ku informatyce ogólnej – ewolucja świadomości

metodologicznej, w: Informatyka a filozofia. Od informatyki i jej zastosowań

do światopoglądu informatycznego, red. P. Stacewicz, Warszawa 2015.

Rubel L., The Extended Analog Computer, „Advances in Applied Mathematics”

(1993) iss. 1, s. 39–50.

Shagrir O., Super-tasks, Accelerating Turing Machines and Uncomputability,

„Theoretical Computer Science” 317 (2004) iss. 1–3, s. 105–114.

Shannon C., Mathematical Theory of the Differential Analyzer, „Journal of

Mathematics and Physics” 20 (1941) iss. 1–4, s. 337–354.

Stacewicz P., Analogowość, analogiczność, ciągłość, http://marciszewski.eu

/?p=8365 (7.03.2017).

Stacewicz P., Obliczenia naturalne i quasi-naturalne, http://marciszewski.eu

/?p=8745 (7.03.2017).

Turing A. M., Computing Machinery and Intelligence, „Mind” 59 (1950)

no. 236, s. 433–460.

Turing A. M., On Computable Numbers, with an Application to the Entscheidungsproblem,

„Proceedings of the Royal Society of London” (1936) no.

, s. 230–265.

Downloads

Published

2018-07-31

Issue

Section

Artykuły