Show The Graduate Center Menu
 
 

Infinite Computing

Ph.D. Program in Computer Science
Spring 2015
Professor Lou D’Alotto
ldalotto@york.cuny.edu or ldalotto@gc.cuny.edu
 
Course Description:
Arithmetic is a branch of mathematics that studies finite numbers and we all have written numerous computer programs that dealt, in some form or another, with arithmetic computations. However our arithmetic computational abilities halt at infinity, both by hand and with a computer. On the opposite end of the number line, close to 0, numbers may be too minuscule (infinitesimals) for proper representation in a computer. In this course we will discuss methods on how to handle infinity and infinitesimals in a computer. Topics include numbers, numerals, infinity number sets, paradoxes of infinite sets, The infinite unit axiom, arithmetical operations and computations assuming the infinite unit axiom, Turing machines, infinite strings and automata on infinite strings. This is a very new and fresh field with a lot of potential applications and research problems. Throughout the course we will discuss many open problems and research directions.
 
Recommended Textbook: 
Sergeyev, Y. D., Arithmetic of Infinity, Edizioni Orizzonti Meridionali, 2003, Italy
We will also look at various papers and articles, many which can be found at:
www.grossone.com/arithmetic.html

Other references:
  1. D’Alotto, L. A. (2014) A classification of one-dimensional cellular au-tomata using infinite computations, Applied Mathematics and Computation, Elsevier, http://dx.doi.org/10.1016/j.amc.2014.06.087
  2. G. Lolli (2012) Infinitesimals and infinities in the history of Mathematics: A brief survey, Applied Mathematics and Computation, 218(16), 7979-7988.
  3. Khoussainov, B., and Nerode, A., Automata Theory and its Applications, Birkhauser, 2001.
  4. Montagna, F., Simi, G., Sorbi, A., (2014) Taking the Pirah˜ a seriously, Commun Nonlinear Sci Numer Simulat, Elsevier, http://dx.doi.org/10.1016/j.cnsns.2014.06.052
  5. Sergeyev, Ya.D., Garro A. (2010) Observability of Turing Machines: a refinement of the theory of computation, Informatica, 21(3), 425-454.
  6. Sergeyev, Ya.D. (2009) Numerical computations and mathematical modelling with infinite and infinitesimal numbers, Journal of Applied Mathematics and Computing, 29, 177-195.
 
Course Goal:
The goal of the course is straightforward: To understand computations with infinity and develop a new and relatively simple way of looking of arithmetic of the infinite that would increase our computational power and permit us to do computations with infinity and infinitesimals as we would with finite numbers.  We will understand and pose possible open problems and applications, using this new methodology, to automata on infinite strings.
 
Course Syllabus:
  1. Real numbers, extended real numbers, infinite countable and uncountable sets Cantor’s Continuum Hypothesis and Hilbert’s First problem (Week1)
  2. Numbers, Numerals, and Paradoxes of Infinity, Hilbert’s Grand Hotel (Week 2)
  3. Some Philosophical foundations of infinity (Week 2, continued)
  4. Treating infinity with limits (Week 2 continued)
  5. The Infinite unit axiom and the cardinality of the natural numbers (Week 3)
  6. Cardinality of other infinite number sets and the real numbers under the Infinite Unit Axiom (Week 3 continued)
  7. Arithmetical operations under the infinite unit axiom and limits (Week 4)
  8. Solutions to paradoxes of infinity (Week 4 continued)
  9. Examples of applications (numerical examples, fractal examples) (Week 5)
  10. Computing with infinite numbers (Week 6)
  11. Theory of Buchi Automata and automata on infinite strings, complementation for Buchi Automata (Weeks 6 continued - 8)
  12. Theory of Rabin Automata and automata on infinite trees (weeks 8 continued - 10)
  13. Automata on infinite strings and Turing machines also Turing machines with the new methodology (Weeks 11 - 14)
  • (a) Computable sequences
  • (b) Applications to infinite games
  • (c) Deterministic and Non-deterministic Turing machines
  • (d) Multi-tape turing machines: Do they really have the same computational power as a single tape?
  • (e) Applications to Cellular Automata
  • (f) Open problems using the infinite unit axiom and applications to Buchi, Rabin automata, and Turing machines
 
Brief Introduction and Background:
The way in which we understand numbers and infinity has to do with that which we are comfortable. That in which we accept and which we believe.  Indeed, most of us accept that 1 + ∞ = ∞ and ∞ + ∞ = ∞. Of course the elements ∞ and −∞ do not belong to the set of real numbers and arithmetic operations do not easily carry over to the extended reals and hence ∞. However we accept the facts that infinity plus any number is infinity and infinity times any positive number is also infinity. The fact that 1 + ∞ = ∞ is not a unique concept to just our culture nor is it a unique concept to only mathematicians and computer scientists. The Pirah˜ a tribe of central Brazil have long used this concept. However they make the conventions 1+1 = 2 and 1+2 = many. Also, in their culture and similar to our 1 + ∞ = ∞, the Pirah˜ a use the convention 1 + many = many. The difference between the Pirah˜ a’s and our numeral system is that ours is obviously more accurate. Once the numbers become larger than 2, the Pirah˜ a cannot distinguish them. In this light, we can probably conjecture that our computational difficulty in working with infinity is not that of the nature of infinity but a consequence of an inadequate numeral system.  In this course we will study the inadequacies and paradoxes of our numeral system and describe a new methodology for handling computations with infinite and infinitesimal numbers and computations on infinite strings. We will also work and compute with infinity and infinite strings (using Buchi and Rabin automata), infinitesimals, explore what it means to be “Turing Computable” in this new paradigm.

Assessment: Assignments and a class presentation.
 
For further information please email me at one of the above addresses.