2.5 SEMI-COMPUTABLE RELATIONS; UNSOLVABILITY

We next define a images-counterpart of images* and imagesimages* and look into some of its closure properties.

2.5.0.3 Definition. (Semi-computable Relations) A relation P(images) is called semi-computable or semi-recursive iff for some f images images, we have, for all imagesn,

images

The set of all semi-computable relations is denoted by images*.

If images in (1) above, then we say that “a” is a semi-computable index ...

Get Theory of Computation now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.