91Ó°ÊÓ

(For those knowing some group theory) Show that the word problem for any finitely presented group is partially decidable.

Show that there is no total computable function \(f(x, y)\) with the following property: if \(P_{x}(y)\) stops, then it does so in \(f(x, y)\) or fewer steps. (Hint. Show that if such a function exists, then the Halting problem is decidable.)

A finite set \(S\) of \(3 \times 3\) matrices is said to be mortal if there is a finite product of members of \(S\) that equals the zero matrix. Show that the predicate ' \(S\) is mortal' is partially decidable. (It has been shown that this problem is nor decidable; see Paterson [1970].)

Suppose that \(M(x)\) and \(N(x)\) are partially decidable; prove that the predicates ' \(M(x)\) and \(N(x)^{\prime}\) ', " \(M(x)\) or \(N(x)^{\prime}\) are partially decidable. Show that the predicate "not \(M(x)\) ' is not necessarily partially decidable.

Suppose that \(M(x, y)\) is partially decidable. Show that (a) ' \(\exists y

Show that the following predicates are diophantine. (a) ' \(x\) is even', (b) " \(x\) divides \(y\) ".

Suppose that \(M\left(x_{1}, \ldots, x_{e}\right)\) is partially decidable and \(g_{1}, \ldots, g_{*}\) are computable partial functions. Show that the predicate \(N(y)\) given by \(N(y)=M\left(g_{1}(y), \ldots, g_{m}(y)\right)\) is partially decidable. (We take this to mean that \(N(y)\) does not hold if any one of \(g_{2}(y), \ldots, g_{n}(y)\) is undefined.)