Show that if K(x) were computable, we could use the following procedure to create a short description for an incompressible string: function incompressible(n: integer) { for x ∈ {0, 1} n if K(x) >= n then output x }

7. design a circuit with three inputs (x, y, and z) representing the bits in a binary number, and three outputs (a, b, and c) also representing bits in a binary number. when the input is 1, 2, or 3, the binary output should be one lesser than the input. when the input is 4, 5, or 6, the binary output should be one greater than the input. when the input is 0, the output is 0, and when the input is 7, the output is 7. show your truth table, all computations for simplification, and the final circuit.