Ways to Compute in Euclidean Frameworks

摘要

This tutorial presents what kind of computation can be carried out inside a Euclidean space with dedicated primitives—and discrete or hybrid (continuous evolution between discrete transitions) time scales. The presented models can perform Classical (Turing, discrete) computations as well as, for some, hyper and analog computations (thanks to the continuity of space). The first half of the tutorial presents three models of computation based on respectively: ruler and compass, local constraints and emergence of polyhedra and piece-wise constant derivative. The other half concentrates on signal machines: line segments are extended and replaced on meeting. These machines are capable hyper-computation and analog computation and to solve PSPACE-problem in "constant space and time" though partial fractal generation.