Reference no: EM132271899

1. Numbered sets. Substantiate that sets are numbered:
a) Set Z³, consists of all three (a ,b, c), where a, b, c - integers;
b) Set GRAPHS, consists of all graphs G with final number (not endless) of vertices.

2. Reductions. Look at the problem HALTING3, where input data consists of Turing Machine program M and three input strings x, y, z and HALTING3 (M, x, y, z), if M stops on each of these strings. Prove that HALTING3 ≤ HALTING, where HALTING - ordinary stop problem.

3. Algorithmic non resolvability. Prove that problems below cannot to be algorithmically solved:
a) A(M) = 1, if M - Turing Machine program and if M runs on empty input strings, Turing Machine stops and print 1.
b) B(M) = 1, if M - Turing Machine program and there does not have any input for string length 2, 4, 6, 8, on which M stops.
c) C(M, x, q) = 1, if M - Turing Machine program, x - input data, q - state. On input data x Turing Machine M somewhen comes into state q.

4. Partial resolvability. Lets look at the problem MORTAL-MATRIX, where given matrices M₁, ..., M_k and have to print answer 1, if a multiplication M_i1M_i2 ... M_im, can be created from these matrices. Multiplication equal to the matrix, where all the elements are equally with 0. Substantiate that MORTAL-MATRIX ir partial solved (algorithmically numbered).