Consider two sets A and B which are both decidable, i.e. both A and B have their own deciders M and N respectively. Prove the following sets are also decidable (i.e. using M and/or N, build a decider for the following sets): 

(a) A ∩ B 

(b) A¯ (the complement of A).

Transcribed Image Text:

A prime number is a positive whole number whose only divisors are itself and 1. Let P = {n: n is a prime number} be the set of all primes. (a) Show that P is a decidable set. That is, build a TMT such that on input n. M accepts n if n is a prime number and rejects otherwise. (b) Using your T from above, build a TM N such that on input n. N prints the nth smallest prime (eg N (8) = 19). Note that your TM N should not perform any division and should exclusively use your decider T to determine if a number is prime. A prime number is a positive whole number whose only divisors are itself and 1. Let P = {n: n is a prime number} be the set of all primes. (a) Show that P is a decidable set. That is, build a TMT such that on input n. M accepts n if n is a prime number and rejects otherwise. (b) Using your T from above, build a TM N such that on input n. N prints the nth smallest prime (eg N (8) = 19). Note that your TM N should not perform any division and should exclusively use your decider T to determine if a number is prime.

Answer rating: 100% (QA)

a To show that the set P of prime numbers is decidable we can create a Turing machine T that accepts a positive integer n as input and decides whether ... View the full answer