When possible, use Rice's Theorems, Griebach's Theorem, and the Post Correspondence Problem rather than direct reductions. L contains at least two strings.
L is infinite.
L is context-free. We can consider the output of a TM to be what is on the tape when it halts. A CFG is linear if no right side of a production has more than one instance of a variable. Remember that regular grammars are right-linear, and thus linear. Show that PCP is decidable for words over a one-symbol alphabet.