Introduction and definitions Computability and undecidability

Jérôme Durand-Lose

Description

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

Informations

• Publié par: pefav
• Nombre de lectures: 84
• Langue: English
• Poids de l'ouvrage: 2 Mo

Extrait

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