//img.uscri.be/pth/81ffca0e29875c97dc282311cea3acf2ab3970c8
Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

Abstract geometrical computation: small Turing universal signal machines

De
28 pages
Abstract geometrical computation: small Turing universal signal machines Abstract geometrical computation: small Turing universal signal machines Jerome Durand-Lose Laboratoire d'Informatique Fondamentale d'Orleans, Universite d'Orleans, Orleans, FRANCE IW Complexity of Simple Programs December 6-7, 2008 – Cork, Irland

  • laboratoire d'informatique fondamentale d'orleans

  • continuous time

  • small turing universal

  • collision rules

  • idealization continuous


Voir plus Voir moins

Abstract geometrical computation: small Turing universal signal machines
Abstract geometrical computation:
small Turing universal signal machines
J´eroˆme Durand-Lose
Laboratoire d’Informatique Fondamentale d’Orl´eans,
´Universit´e d’Orl´eans, Orleans, FRANCE
IW Complexity of Simple Programs
December 6-7, 2008 – Cork, IrlandAbstract geometrical computation: small Turing universal signal machines
1 Introduction
2 Turing machines
3 Cellular automata
4 Cyclic tag systems
5 ConclusionAbstract geometrical computation: small Turing universal signal machines
Introduction
1 Introduction
2 Turing machines
3 Cellular automata
4 Cyclic tag systems
5 ConclusionAbstract geometrical computation: small Turing universal signal machines
Introduction
Context
Collision based computing
Idealization
continuous space
continuous time
dimensionless particles/signalsAbstract geometrical computation: small Turing universal signal machines
Introduction
Abstract geometrical computation
Signal machines
meta-signals (finitely many)
their speed/velocity
collision rules
Signals, e.g.
red (with speed 1) at position xx
blue (with speed -1) at position yy
Collision, e.g.
rule{green, red}→{blue}
applicationAbstract geometrical computation: small Turing universal signal machines
Introduction
An example
Space
TimeAbstract geometrical computation: small Turing universal signal machines
Introduction
More examplesAbstract geometrical computation: small Turing universal signal machines
Introduction
More complex examplesAbstract geometrical computation: small Turing universal signal machines
Turing machines
1 Introduction
2 Turing machines
3 Cellular automata
4 Cyclic tag systems
5 ConclusionAbstract geometrical computation: small Turing universal signal machines
Turing machines
Turing machines?
q Finite automata
Read/write head
...^ input Tape# #