Abstract geometrical computation: small Turing universal signal machines

Jérôme Durand-Lose

Description

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

Sujets

• Continuous-time stochastic process

Informations

• Publié par: pefav
• Nombre de lectures: 16
• Langue: English

Extrait

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# #