Introduction and definitions Computability and undecidability

pages

English

Documents

Écrit par
Jérôme Durand-Lose

Publié par
pefav

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

pages

English

Ebook

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Publié par

pefav

Nombre de lectures

Langue

English

Poids de l'ouvrage

2 Mo

Introduction and definitions Computability and undecidability Abstract geometrical computation: Turing-computing ability and undecidability Jerome Durand-Lose Laboratoire d'Informatique Fondamentale d'Orleans, Universite d'Orleans, Orleans, FRANCE CiE 2005: New Computational Paradigms Amsterdam, June 8th, 2005 Jerome Durand-Lose Abst. geom. comp.: computability and undecidability

introduction signal

laboratoire d'informatique fondamentale d'orleans

qz bi-infinite

turing-computing ability

space time diagrams

counter automata

Voir

Publié par

pefav

Nombre de lectures

Langue

English

Poids de l'ouvrage

2 Mo

Introduction and deﬂnitions
Computability and undecidability
Abstract geometrical computation:
Turing-computing ability and undecidability
J¶er^ ome Durand-Lose
Laboratoire d’Informatique Fondamentale d’Orl¶eans,
Universit¶e d’Orl¶eans, Orleans¶ , FRANCE
CiE 2005: New Computational Paradigms
Amsterdam, June 8th, 2005
J¶er^ ome Durand-Lose Abst. geom. comp.: computability and undecidabilityIntroduction and deﬂnitions
Computability and undecidability
Introduction
Deﬂnitions
Signal machines
Computability
2-counter automata simulation
Undecidability
Conclusion
J¶er^ ome Durand-Lose Abst. geom. comp.: computability and undecidabilityIntroduction and deﬂnitions Introduction
Computability and undecidability Signal machines
Starting from discrete model...
Cellular automata
ZQ
bi-inﬂnite line of states
jQj <1
Zcontinuous dynamical system over Q
9
local >=parallel Zupdating of Q
synchronous >;
uniform
J¶er^ ome Durand-Lose Abst. geom. comp.: computability and undecidabilityIntroduction and deﬂnitions Introduction
Computability and undecidability Signal machines
...with discrete space-time diagrams
[HSC01, Fig. 7]
[BNR91, Fig. 7]
[Siw01, Fig. 5]
J¶er^ ome Durand-Lose Abst. geom. comp.: computability and undecidabilityIntroduction and deﬂnitions Introduction
Computability and undecidability Signal machines
...with discrete space-time diagrams
[LN90, Fig. 3][LN90, Fig. 4]
J¶er^ ome Durand-Lose Abst. geom. comp.: computability and undecidabilityIntroduction and deﬂnitions Introduction
Computability and undecidability Signal machines
...with discrete space-time diagrams
[Got66, Fig. 3]
[Got66, Fig. 6]
J¶er^ ome Durand-Lose Abst. geom. comp.: computability and undecidabilityIntroduction and deﬂnitions Introduction
Computability and undecidability Signal machines
...with discrete space-time diagrams
[VMP70, Fig. 3][VMP70, Fig. 1] [VMP70, Fig. 2]
J¶er^ ome Durand-Lose Abst. geom. comp.: computability and undecidabilityIntroduction and deﬂnitions Introduction
Computability and undecidability Signal machines
...with discrete space-time diagrams
1
Bits 1 of the (2n, 2t(n))
multiplier
0 E1
Bits 0 of the D
multiplier 1
1 Bit "end " of *
the multiplier
T D
2
Bits 1 of the 0
multiplicand0 E-1
<1 Bits 0 of the
multiplicand
0
0
Bit "end" of
the multiplicand
E
0 0
Limits of a
computation
0
0 Bits 0 in transit
throught the Time f(n)
network
1
Bits 1 in transit
0 throught the
network
1
Time f(5)
1 0
Signal T
Time f(4)
0 * Signal D
k / 20 *
1
Time f(3) Signal D0 0 k
1
0 1 Signal E
1 0
0 Time f(2)
0 Signal E - 1
0 1
Time f (1)1 Signal E
+ 1
1
Time 01
0 Cell 0
[Fis65, Fig. 2]
[Maz96, Fig. 8] [MT99, Fig. 18]
J¶er^ ome Durand-Lose Abst. geom. comp.: computability and undecidability
0
0
0
0
5
J

0
5
0
&&
11

11
?
##
B
"
)
"

!

!

!
9;:
!
A
!
5

5

J

((

%

33

/

/

/
)
/
7
/
=
/
8
/
9
/
@

EFD

9

9

L

M

)

''

%
22
$$
22
33

4

6

8

<

>

@

@

B
/
8
..
C

B

D

G
..
?
-
H
-
B
-
H;I
,
K
,
I
+
M
+
N
+
)
+
)
+
((
**
''
**
&&

%

$$

##
Introduction and deﬂnitions Introduction
Computability and undecidability Signal machines
(Discrete) Space-time diagrams
ImplementationObservation
Discrete lines
Interpretation Discretization
Lines on the plane
Dynamics Conception
J¶er^ ome Durand-Lose Abst. geom. comp.: computability and undecidability