Geometrical model of computation: fractals and complexity gaps
type: Dataset
contact point: Organization
  fn: CCSD
keyword: infoinfo-dmcomputer-science-csdiscrete-mathematics-csdm
keyword: calcul-geometrique
keyword: geometrical-computation
keyword: calcul-non-conventionnel
keyword: signal-machines
keyword: unconventional-computing
keyword: computational-complexity
keyword: fractals
keyword: infoinfo-cccomputer-science-cscomputational-complexity-cscc
keyword: machines-a-signaux
keyword: theses
keyword: modele-de-calcul
keyword: fractales
keyword: complexite-de-problemes
keyword: infoeu-reposemanticsdoctoralthesis
keyword: model-of-computation
landing page: https://theses.hal.science/tel-00870600
description: Geometrical models of computation allow to compute by using geometrical elementary operations. Among them, the signal machines model distinguishes itself by its simplicity, along with its power to realize efficiently various computations. We propose here an illustration and a study of this ability, especially in the case of massively parallel processes. We show first, throught a study of fractals, that signal machines are able to make a massive and parallel use of space. Then, a framework of geometrical modular programmation is proposed for designing machines from basic geometrical components --called modules-- supplied with given functionnalities. This method fits particulary with the conception of geometrical parallel computations. Finally, the joint use of this method and of fractal structures provides a geometrical resolution of difficult problems such as the boolean satisfiability problems SAT and Q-SAT. These ones, as well as several variants, are solved by signal machines with a model-specific time complexity, called collisions depth, which is polynomial, illustrating thus the efficiency and the parallel computational abilities of signal machines.
issued: 2026-05-06T19:43:20.714309
language: fr
modified: 2026-05-06T19:43:20.714313

test_moissonnage_selune
type: Agent

Geometrical model of computation: fractals and complexity gaps
type: Distribution
access URL: https://theses.hal.science/tel-00870600
format: HTML
issued: 2026-05-06T19:43:20.735920
modified: 2026-05-06T19:43:20.694275