Therefore, to calculate A(1, 1), we have
A
A
A A
A A
( , )
(
,
)
( , ( , )) (
( , ( , )
1 1
0 1 0 1
0 10
0 01
=
+
+
=
using (3))
=
) (
( , )
(
(
using (2))
=
using (1))
(1,1) = 3
using (1))
A 0 2
A
A
A
A A
( , )
(
,
)
( , ( , )
(
2 2
1 1 1 1
1 21
=
+
+
=
using (3))
Now,
A
A
A A
A A
( , )
(
,
)
( , ( , )
(
( , ( , ))
21
1 1 0 1
1 2 0
1 11
=
+
+
=
using (3))
=
(
( , ( , ))
( , )
(
,
)
( , ( ,
using (2))
= A A
A
A
A A
1 11
1 3
0 1 2 1
0 1 2
=
=
+
+
=
))
(using (3))
= A(0, 4)
A(2,1) = 5.
There fore,
A
A A
A
( , )
( , ( , ))
( , )
2 2
1
2 1
1 5
=
=
Now,
A
A
A A
A
( , )
(
,
)
( , ( , ))
( , )
1 5
0 1 4 1
0 1 4
1
1 4
=
+
+
=
+
(Using (3))
=
(Using (1))
= 1
0 1 3 1
1
0 1 3
1 1
1 3
1
+
+
+
= +
= + +
=
A
A A
A
(
,
)
( , ( , ))
( , )
+ + +
= + + +
=
1 1
1 2
1 1 1 4
1 5 7
A
A
( , )
( , )
.
Therefore A(2, 2) = 7.
GLOSSARY
Formal system: Should be complete and consistent.
Completeness: Should be possible either to prove or disprove any
proposition that can be expressed in the system.
Consistency: Should not be possible to both prove and disprove a proposition
in the system.
Russel’s Paradox: Consider the set of all sets that do not have themselves as
a member. Is this set a member of itself?
230
Theory of Automata, Formal Languages and Computation