21. What is the ‘weak form’ of Turing Thesis?
“A Turing machine can compute anything that can be computed by a
general-purpose digital computer.” This is the weak form of Turing
Thesis.
22. What is the ‘strong form’ of Turing Thesis?
“A Turing Machine can compute anything that can be computed”.
This is the strong form of Turing Thesis.
23. When is a language said to be recursively enumerable?
A language is recursively enumerable if there exists a Turing
machine that accepts every string of the language, and does not accept
strings that are not in the language.
24. What is the Post’s correspondence problem?
Let Σ be a finite alphabet, and let A and B be the lists of nonempty
strings over Σ, with | | | |,
A B
=
i.e.,
A w w
w k
= ( , ,
)
1
2 KK
and
B
x x
x k
= ( , ,
)
1
2 KK
.
Post’s correspondence problem is the following:
“Does there exist a sequence of integers i i
i m
1 2
, , K such that m ≥ 1
and
w w w
w
x x x
x
i
i
i
im
i
i i
im
1 2 3
1
2 3
KK
KK
=
?”
Turing Machines
209