This popular meme originated in the era of 'Good Old Fashioned AI' (GOFAI), when the belief was that intelligence could usefully be defined entirely in terms of logic.
The meme seems to rely on the AI parsing commands using a theorem prover, the idea presumably being that it's driven into some kind of infinite loop by trying to prove an unprovable or inconsistent statement.
Nowadays, GOFAI methods have been replaced by 'environment and percept sequences', which are not generally characterized in such an inflexible fashion. It would not take a great deal of sophisticated metacognition for a robot to observe that, after a while, its deliberations were getting in the way of useful work.
Rodney Brooks touched on this when speaking about the behavior of the robot in Spielberg's AI film, (which waited patiently for 5,000 years), saying something like "My robots wouldn't do that - they'd get bored".
EDIT: If you really want to kill an AI that operates in terms of percepts, you'll need to work quite a bit harder. This paper (which was mentioned in this question) discusses what notions of death/suicide might mean in such a case.