Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
The Journal of Supercomputing
Published in: The Journal of Supercomputing 2/2013

01-08-2013

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

Authors: Yaroslav D. Sergeyev, Alfredo Garro

Published in: The Journal of Supercomputing | Issue 2/2013

Log in

Activate our intelligent search to find suitable subject content or patents.

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.
previous article Efficient application of GPGPU for lava flow hazard mapping
next article Cellular automata on FPGA for real-time urban traffic signals control

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
Footnotes
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.
 
Literature
1.
Adamatzky A, De Lacy Costello B, Asai T (2005) Reaction-diffusion computers. Elsevier, Amsterdam
2.
Ausiello G, D’Amore F, Gambosi G (2006) Linguaggi, modelli, complessità, 2nd edn. Franco Angeli Editore, Milan
3.
4.
Cantor G (1955) Contributions to the founding of the theory of transfinite numbers. Dover Publications, New York
5.
6.
7.
Cooper SB (2003) Computability theory. Chapman Hall/CRC, New York
8.
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
9.
10.
Davis M (1985) Computability & unsolvability. Dover, New York
11.
Gödel K (1931) Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme. Monatshefte Math Phys 38:173–198
12.
Gordon P (2004) Numerical cognition without words: evidence from Amazonia. Science 306(15):496–499 CrossRef
13.
Hopcroft J, Ullman J (1979) Introduction to automata theory, languages and computation, 1st edn. Addison-Wesley, Reading MATH
14.
Iudin DI, Sergeyev YD, Hayakawa M (2012) Interpretation of percolation in terms of infinity computations. Appl Math Comput 218(16):8099–8111 MathSciNetMATHCrossRef
15.
Kleene SC (1952) Introduction to metamathematics. D. Van Nostrand, New York MATH
16.
Kolmogorov AN (1953) On the concept of algorithm. Usp Mat Nauk 8(4):175–176 MATH
17.
Kolmogorov AN, Uspensky VA (1958) On the definition of algorithm. Usp Mat Nauk 13(4):3–28 MATH
18.
Leibniz GW, Child JM (2005) The early mathematical manuscripts of Leibniz. Dover, New York
19.
Levi-Civita T (1898) Sui numeri transfiniti. Rend Accad Lincei, Ser 5a 113:7–91
20.
21.
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.
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.
Markov Jr. AA, Nagorny NM (1996) Theory of algorithms, 2nd edn. FAZIS, Moscow MATH
24.
Mayberry JP (2001) The foundations of mathematics in the theory of sets. Cambridge University Press, Cambridge CrossRef
25.
26.
Nielsen M, Chuang I (2000) Quantum computation and quantum information. Cambridge University Press, Cambridge MATH
27.
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.
Robinson A (1996) Non-standard analysis. Princeton Univ Press, Princeton MATH
30.
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.
Sergeyev YD (2003) Arithmetic of infinity. Edizioni Orizzonti Meridionali, CS MATH
32.
Sergeyev YD (2007) Blinking fractals and their quantitative analysis using infinite and infinitesimal numbers. Chaos Solitons Fractals 33(1):50–75 CrossRef
33.
Sergeyev YD (2008) A new applied approach for executing computations with infinite and infinitesimal quantities. Informatica 19(4):567–596 MathSciNetMATH
34.
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.
Sergeyev YD (2009) Numerical computations and mathematical modelling with infinite and infinitesimal numbers. J Appl Math Comput 29:177–195 MathSciNetMATHCrossRef
36.
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.
Sergeyev YD (2010) Counting systems and the first Hilbert problem. Nonlinear Anal Ser A, Theory Methods Appl 72(3–4):1701–1708 MathSciNetMATHCrossRef
38.
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
39.
40.
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.
Sergeyev YD (2011) Using blinking fractals for mathematical modelling of processes of growth in biological systems. Informatica 22(4):559–576 MathSciNetMATH
42.
Sergeyev YD, Garro A (2010) Observability of Turing machines: a refinement of the theory of computation. Informatica 21(3):425–454 MathSciNetMATH
43.
Turing AM (1936–1937) On computable numbers, with an application to the entscheidungsproblem. Proc Lond Math Soc, Ser 2 42:230–265
44.
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.
Žilinskas A, Žilinskas J (2010) Interval arithmetic based optimization in nonlinear regression. Informatica 21(1):149–158 MathSciNetMATH
46.
47.
Walster GW (2000) Compiler support of interval arithmetic with inline code generation and nonstop exception handling. Tech Report, Sun Microsystems
48.
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.
Ž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
Metadata
Title
Single-tape and multi-tape Turing machines through the lens of the Grossone methodology
Authors
Yaroslav D. Sergeyev
Alfredo Garro
Publication date
01-08-2013
Publisher
Springer US
Published in
The Journal of Supercomputing / Issue 2/2013
Print ISSN: 0920-8542
Electronic ISSN: 1573-0484
DOI
https://doi.org/10.1007/s11227-013-0894-y

Other articles of this Issue 2/2013

The Journal of Supercomputing 2/2013 Go to the issue

OriginalPaper

Agent-based accountable grid computing systems

OriginalPaper

A flexible and dynamic page migration infrastructure based on hardware counters

OriginalPaper

Design and formal verification of a hierarchical cache coherence protocol for NoC based multiprocessors

OriginalPaper

Corrosion-passivation processes in a cellular automata based simulation study

OriginalPaper

Cellular automata on FPGA for real-time urban traffic signals control

OriginalPaper

The number of DFAs for a given spanning tree

Premium Partner

    Image Credits