Let M be a machine that takes a natural number as input and outputs a natural number.
Let L = $\{M:\;M(n)\;outputs\;a\;prime\;greater\;than\;n\;for\;every\;n\}$
Is L decidable?
Is L recognizable?
Intuitively, my thoughts are that L is neither recognizable or decidable since any algorithm to decide/recognize L would have to test an infinite set of inputs.
However, I'm not sure how to reduce the Halting Problem to this problem to prove that. I'm not even sure if that is the appropriate method of proof. Can someone help?
$L$ is not recognizable (hence not decidable either):
Suppose $L$ is recognizable. Construct $M_{e,x}$ as follows: take an input $n$ and simulate the computation of $\phi_e(x)$ (where $\phi_e$ is a Turing machine with a Godel number $e$) for $n$ steps. If $\phi_e(x) \downarrow_n$ (halts after at most $n$ steps), then output $0$, otherwise output a prime number greater than $n$.
As an exercise show that $\forall e,x. \phi_e(x) \uparrow \iff M_{e,x} \in L$.
Then $\phi_e(x) \downarrow$ recognizable trivially. $\phi_e(x) \uparrow$ if $M_{e,x} \in L$, hence recognizable. Therefore the halting problem $H=\{\langle e, x \rangle | \phi_e(x) \downarrow \}$ is decidable. Contradiction.