Introduction and definitions Computability and undecidability
25
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 !
25
pages
English
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
- introduction signal
- laboratoire d'informatique fondamentale d'orleans
- qz bi-infinite
- turing-computing ability
- space time diagrams
- counter automata
Introduction and deflnitions
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 deflnitions
Computability and undecidability
Introduction
Deflnitions
Signal machines
Computability
2-counter automata simulation
Undecidability
Conclusion
J¶er^ ome Durand-Lose Abst. geom. comp.: computability and undecidabilityIntroduction and deflnitions Introduction
Computability and undecidability Signal machines
Starting from discrete model...
Cellular automata
ZQ
bi-inflnite 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 deflnitions 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 deflnitions 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 deflnitions 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 deflnitions 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 deflnitions 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 deflnitions 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
