Skip to main content
Erschienen in: The Journal of Supercomputing 2/2013

01.08.2013

Single-tape and multi-tape Turing machines through the lens of the Grossone methodology

verfasst von: Yaroslav D. Sergeyev, Alfredo Garro

Erschienen in: The Journal of Supercomputing | Ausgabe 2/2013

Einloggen

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

The paper investigates how the mathematical languages used to describe and to observe automatic computations influence the accuracy of the obtained results. In particular, we focus our attention on single and multi-tape Turing machines, which are described and observed through the lens of a new mathematical language, which is strongly based on three methodological ideas borrowed from physics and applied to mathematics, namely: the distinction between the object (we speak here about a mathematical object) of an observation and the instrument used for this observation; interrelations holding between the object and the tool used for the observation; the accuracy of the observation determined by the tool. Results of the observation executed by the traditional and new languages are compared and discussed.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Fußnoten
1
We are reminded that a numeral is a symbol or group of symbols that represents a number. The difference between numerals and numbers is the same as the difference between words and the things they refer to. A number is a concept that a numeral expresses. The same number can be represented by different numerals. For example, the symbols “7,” “seven,” and “VII” are different numerals, but they all represent the same number.
 
2
This similarity becomes even more pronounced if one considers another Amazonian tribe—Mundurukú (see [27])—who fail in exact arithmetic with numbers larger than 5 but are able to compare and add large approximate numbers that are far beyond their naming range. Particularly, they use the words ‘some, not many’ and ‘many, really many’ to distinguish two types of large numbers using the rules that are very similar to ones used by Cantor to operate with ℵ0 and ℵ1, respectively.
 
3
Analogously, when the switch from Roman numerals to the Arabic ones has been done, numerals X, V, I, etc. have been excluded from records using Arabic numerals.
 
4
It is worthy to notice a deep relation of this observation to the Axiom of Choice. Since Theorem 1 states that any sequence can have at maximum ① elements, so this fact holds for the process of a sequential choice, as well. As a consequence, it is not possible to choose sequentially more than ① elements from a set. This observation also emphasizes the fact that the parallel computational paradigm is significantly different with respect to the sequential one because p parallel processes can choose https://static-content.springer.com/image/art%3A10.1007%2Fs11227-013-0894-y/MediaObjects/11227_2013_894_IEq48_HTML.gif elements from a set.
 
Literatur
1.
Zurück zum Zitat Adamatzky A, De Lacy Costello B, Asai T (2005) Reaction-diffusion computers. Elsevier, Amsterdam Adamatzky A, De Lacy Costello B, Asai T (2005) Reaction-diffusion computers. Elsevier, Amsterdam
2.
Zurück zum Zitat Ausiello G, D’Amore F, Gambosi G (2006) Linguaggi, modelli, complessità, 2nd edn. Franco Angeli Editore, Milan Ausiello G, D’Amore F, Gambosi G (2006) Linguaggi, modelli, complessità, 2nd edn. Franco Angeli Editore, Milan
4.
Zurück zum Zitat Cantor G (1955) Contributions to the founding of the theory of transfinite numbers. Dover Publications, New York Cantor G (1955) Contributions to the founding of the theory of transfinite numbers. Dover Publications, New York
7.
Zurück zum Zitat Cooper SB (2003) Computability theory. Chapman Hall/CRC, New York Cooper SB (2003) Computability theory. Chapman Hall/CRC, New York
8.
Zurück zum Zitat De Cosmis S, De Leone R (2012) The use of Grossone in mathematical programming and operations research. Appl Math Comput 218(16):8029–8038 MathSciNetMATHCrossRef De Cosmis S, De Leone R (2012) The use of Grossone in mathematical programming and operations research. Appl Math Comput 218(16):8029–8038 MathSciNetMATHCrossRef
10.
Zurück zum Zitat Davis M (1985) Computability & unsolvability. Dover, New York Davis M (1985) Computability & unsolvability. Dover, New York
11.
Zurück zum Zitat Gödel K (1931) Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme. Monatshefte Math Phys 38:173–198 Gödel K (1931) Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme. Monatshefte Math Phys 38:173–198
12.
Zurück zum Zitat Gordon P (2004) Numerical cognition without words: evidence from Amazonia. Science 306(15):496–499 CrossRef Gordon P (2004) Numerical cognition without words: evidence from Amazonia. Science 306(15):496–499 CrossRef
13.
Zurück zum Zitat Hopcroft J, Ullman J (1979) Introduction to automata theory, languages and computation, 1st edn. Addison-Wesley, Reading MATH Hopcroft J, Ullman J (1979) Introduction to automata theory, languages and computation, 1st edn. Addison-Wesley, Reading MATH
14.
Zurück zum Zitat Iudin DI, Sergeyev YD, Hayakawa M (2012) Interpretation of percolation in terms of infinity computations. Appl Math Comput 218(16):8099–8111 MathSciNetMATHCrossRef Iudin DI, Sergeyev YD, Hayakawa M (2012) Interpretation of percolation in terms of infinity computations. Appl Math Comput 218(16):8099–8111 MathSciNetMATHCrossRef
15.
Zurück zum Zitat Kleene SC (1952) Introduction to metamathematics. D. Van Nostrand, New York MATH Kleene SC (1952) Introduction to metamathematics. D. Van Nostrand, New York MATH
16.
Zurück zum Zitat Kolmogorov AN (1953) On the concept of algorithm. Usp Mat Nauk 8(4):175–176 MATH Kolmogorov AN (1953) On the concept of algorithm. Usp Mat Nauk 8(4):175–176 MATH
17.
Zurück zum Zitat Kolmogorov AN, Uspensky VA (1958) On the definition of algorithm. Usp Mat Nauk 13(4):3–28 MATH Kolmogorov AN, Uspensky VA (1958) On the definition of algorithm. Usp Mat Nauk 13(4):3–28 MATH
18.
Zurück zum Zitat Leibniz GW, Child JM (2005) The early mathematical manuscripts of Leibniz. Dover, New York Leibniz GW, Child JM (2005) The early mathematical manuscripts of Leibniz. Dover, New York
19.
Zurück zum Zitat Levi-Civita T (1898) Sui numeri transfiniti. Rend Accad Lincei, Ser 5a 113:7–91 Levi-Civita T (1898) Sui numeri transfiniti. Rend Accad Lincei, Ser 5a 113:7–91
20.
Zurück zum Zitat Lolli G (2012) Infinitesimals and infinites in the history of mathematics: a brief survey. Appl Math Comput 218(16):7979–7988 MathSciNetMATHCrossRef Lolli G (2012) Infinitesimals and infinites in the history of mathematics: a brief survey. Appl Math Comput 218(16):7979–7988 MathSciNetMATHCrossRef
21.
Zurück zum Zitat Margenstern M (2011) Using Grossone to count the number of elements of infinite sets and the connection with bijections. p-Adic Numbers, Ultrametr Anal Appl 3(3):196–204 MathSciNetMATHCrossRef Margenstern M (2011) Using Grossone to count the number of elements of infinite sets and the connection with bijections. p-Adic Numbers, Ultrametr Anal Appl 3(3):196–204 MathSciNetMATHCrossRef
22.
Zurück zum Zitat Margenstern M (2012) An application of Grossone to the study of a family of tilings of the hyperbolic plane. Appl Math Comput 218(16):8005–8018 MathSciNetMATHCrossRef Margenstern M (2012) An application of Grossone to the study of a family of tilings of the hyperbolic plane. Appl Math Comput 218(16):8005–8018 MathSciNetMATHCrossRef
23.
Zurück zum Zitat Markov Jr. AA, Nagorny NM (1996) Theory of algorithms, 2nd edn. FAZIS, Moscow MATH Markov Jr. AA, Nagorny NM (1996) Theory of algorithms, 2nd edn. FAZIS, Moscow MATH
24.
Zurück zum Zitat Mayberry JP (2001) The foundations of mathematics in the theory of sets. Cambridge University Press, Cambridge CrossRef Mayberry JP (2001) The foundations of mathematics in the theory of sets. Cambridge University Press, Cambridge CrossRef
25.
26.
Zurück zum Zitat Nielsen M, Chuang I (2000) Quantum computation and quantum information. Cambridge University Press, Cambridge MATH Nielsen M, Chuang I (2000) Quantum computation and quantum information. Cambridge University Press, Cambridge MATH
27.
Zurück zum Zitat Pica P, Lemer C, Izard V, Dehaene S (2004) Exact and approximate arithmetic in an amazonian indigene group. Science 306(15):499–503 CrossRef Pica P, Lemer C, Izard V, Dehaene S (2004) Exact and approximate arithmetic in an amazonian indigene group. Science 306(15):499–503 CrossRef
28.
29.
Zurück zum Zitat Robinson A (1996) Non-standard analysis. Princeton Univ Press, Princeton MATH Robinson A (1996) Non-standard analysis. Princeton Univ Press, Princeton MATH
30.
Zurück zum Zitat Rosinger EE (2011) Microscopes and telescopes for theoretical physics: how rich locally and large globally is the geometric straight line? Prespacetime J 2(4):601–624 Rosinger EE (2011) Microscopes and telescopes for theoretical physics: how rich locally and large globally is the geometric straight line? Prespacetime J 2(4):601–624
31.
Zurück zum Zitat Sergeyev YD (2003) Arithmetic of infinity. Edizioni Orizzonti Meridionali, CS MATH Sergeyev YD (2003) Arithmetic of infinity. Edizioni Orizzonti Meridionali, CS MATH
32.
Zurück zum Zitat Sergeyev YD (2007) Blinking fractals and their quantitative analysis using infinite and infinitesimal numbers. Chaos Solitons Fractals 33(1):50–75 CrossRef Sergeyev YD (2007) Blinking fractals and their quantitative analysis using infinite and infinitesimal numbers. Chaos Solitons Fractals 33(1):50–75 CrossRef
33.
Zurück zum Zitat Sergeyev YD (2008) A new applied approach for executing computations with infinite and infinitesimal quantities. Informatica 19(4):567–596 MathSciNetMATH Sergeyev YD (2008) A new applied approach for executing computations with infinite and infinitesimal quantities. Informatica 19(4):567–596 MathSciNetMATH
34.
Zurück zum Zitat Sergeyev YD (2009) Evaluating the exact infinitesimal values of area of Sierpinski’s carpet and volume of Menger’s sponge. Chaos Solitons Fractals 42(5):3042–3046 CrossRef Sergeyev YD (2009) Evaluating the exact infinitesimal values of area of Sierpinski’s carpet and volume of Menger’s sponge. Chaos Solitons Fractals 42(5):3042–3046 CrossRef
35.
Zurück zum Zitat Sergeyev YD (2009) Numerical computations and mathematical modelling with infinite and infinitesimal numbers. J Appl Math Comput 29:177–195 MathSciNetMATHCrossRef Sergeyev YD (2009) Numerical computations and mathematical modelling with infinite and infinitesimal numbers. J Appl Math Comput 29:177–195 MathSciNetMATHCrossRef
36.
Zurück zum Zitat Sergeyev YD (2009) Numerical point of view on calculus for functions assuming finite, infinite, and infinitesimal values over finite, infinite, and infinitesimal domains. Nonlinear Anal Ser A: Theory Methods Appl 71(12):e1688–e1707 MathSciNetMATHCrossRef Sergeyev YD (2009) Numerical point of view on calculus for functions assuming finite, infinite, and infinitesimal values over finite, infinite, and infinitesimal domains. Nonlinear Anal Ser A: Theory Methods Appl 71(12):e1688–e1707 MathSciNetMATHCrossRef
37.
Zurück zum Zitat Sergeyev YD (2010) Counting systems and the first Hilbert problem. Nonlinear Anal Ser A, Theory Methods Appl 72(3–4):1701–1708 MathSciNetMATHCrossRef Sergeyev YD (2010) Counting systems and the first Hilbert problem. Nonlinear Anal Ser A, Theory Methods Appl 72(3–4):1701–1708 MathSciNetMATHCrossRef
38.
Zurück zum Zitat Sergeyev YD (2010) Lagrange lecture: Methodology of numerical computations with infinities and infinitesimals. Rendiconti Sem Mat dell’Univ Politecnico Torino 68(2):95–113 MathSciNetMATH Sergeyev YD (2010) Lagrange lecture: Methodology of numerical computations with infinities and infinitesimals. Rendiconti Sem Mat dell’Univ Politecnico Torino 68(2):95–113 MathSciNetMATH
40.
Zurück zum Zitat Sergeyev YD (2011) On accuracy of mathematical languages used to deal with the Riemann zeta function and the Dirichlet eta function. p-Adic Numbers, Ultrametr Anal Appl 3(2):129–148 MathSciNetMATHCrossRef Sergeyev YD (2011) On accuracy of mathematical languages used to deal with the Riemann zeta function and the Dirichlet eta function. p-Adic Numbers, Ultrametr Anal Appl 3(2):129–148 MathSciNetMATHCrossRef
41.
Zurück zum Zitat Sergeyev YD (2011) Using blinking fractals for mathematical modelling of processes of growth in biological systems. Informatica 22(4):559–576 MathSciNetMATH Sergeyev YD (2011) Using blinking fractals for mathematical modelling of processes of growth in biological systems. Informatica 22(4):559–576 MathSciNetMATH
42.
Zurück zum Zitat Sergeyev YD, Garro A (2010) Observability of Turing machines: a refinement of the theory of computation. Informatica 21(3):425–454 MathSciNetMATH Sergeyev YD, Garro A (2010) Observability of Turing machines: a refinement of the theory of computation. Informatica 21(3):425–454 MathSciNetMATH
43.
Zurück zum Zitat Turing AM (1936–1937) On computable numbers, with an application to the entscheidungsproblem. Proc Lond Math Soc, Ser 2 42:230–265 Turing AM (1936–1937) On computable numbers, with an application to the entscheidungsproblem. Proc Lond Math Soc, Ser 2 42:230–265
44.
Zurück zum Zitat Vita MC, De Bartolo S, Fallico C, Veltri M (2012) Usage of infinitesimals in the Menger’s Sponge model of porosity. Appl Math Comput 218(16):8187–8196 MathSciNetMATHCrossRef Vita MC, De Bartolo S, Fallico C, Veltri M (2012) Usage of infinitesimals in the Menger’s Sponge model of porosity. Appl Math Comput 218(16):8187–8196 MathSciNetMATHCrossRef
45.
Zurück zum Zitat Žilinskas A, Žilinskas J (2010) Interval arithmetic based optimization in nonlinear regression. Informatica 21(1):149–158 MathSciNetMATH Žilinskas A, Žilinskas J (2010) Interval arithmetic based optimization in nonlinear regression. Informatica 21(1):149–158 MathSciNetMATH
46.
Zurück zum Zitat Wallis J (1656) Arithmetica infinitorum Wallis J (1656) Arithmetica infinitorum
47.
Zurück zum Zitat Walster GW (2000) Compiler support of interval arithmetic with inline code generation and nonstop exception handling. Tech Report, Sun Microsystems Walster GW (2000) Compiler support of interval arithmetic with inline code generation and nonstop exception handling. Tech Report, Sun Microsystems
48.
Zurück zum Zitat Zhigljavsky AA (2012) Computing sums of conditionally convergent and divergent series using the concept of Grossone. Appl Math Comput 218(16):8064–8076 MathSciNetMATHCrossRef Zhigljavsky AA (2012) Computing sums of conditionally convergent and divergent series using the concept of Grossone. Appl Math Comput 218(16):8064–8076 MathSciNetMATHCrossRef
49.
Zurück zum Zitat Žilinskas A (2012) On strong homogeneity of two global optimization algorithms based on statistical models of multimodal objective functions. Appl Math Comput 218(16):8131–8136 MathSciNetMATHCrossRef Žilinskas A (2012) On strong homogeneity of two global optimization algorithms based on statistical models of multimodal objective functions. Appl Math Comput 218(16):8131–8136 MathSciNetMATHCrossRef
Metadaten
Titel
Single-tape and multi-tape Turing machines through the lens of the Grossone methodology
verfasst von
Yaroslav D. Sergeyev
Alfredo Garro
Publikationsdatum
01.08.2013
Verlag
Springer US
Erschienen in
The Journal of Supercomputing / Ausgabe 2/2013
Print ISSN: 0920-8542
Elektronische ISSN: 1573-0484
DOI
https://doi.org/10.1007/s11227-013-0894-y

Weitere Artikel der Ausgabe 2/2013

The Journal of Supercomputing 2/2013 Zur Ausgabe