Abstract geometrical computation: small Turing universal signal machines
28
pages
English
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Découvre YouScribe et accède à tout notre catalogue !
Découvre YouScribe et accède à tout notre catalogue !
28
pages
English
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
- laboratoire d'informatique fondamentale d'orleans
- continuous time
- small turing universal
- collision rules
- idealization continuous
Publié par
Langue
English
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# #
