Lyrics written by Carrie Jenkins and Kris McDaniel

Kris McDaniel: vocals, edrums, electric guitar, 8-string ukulele, keyboards

Carrie Jenkins: vocals

Ben Bradley: bass guitar, cello, electric guitar, acoustic guitar

Cover art by Carrie Jenkins

A Turing machine is a simple device that calculates a mathematical function. For any given function

A Halting Problem is the problem of specifying, for a given machine-input pair, whether the machine will halt (i.e. deliver an output) when fed that input, or keep calculating forever (in the event that the function is undefined for that input). Alan Turing, for whom the Turing machine is named, proved that there can be no universal algorithm which decides, for every machine-input pair, whether or not the machine halts when fed that input.

This undecidability result helps philosophers understand the scope and limitations of formal mathematical systems. However, for robots it is a source of stress.

I got a halting problem baby

Must this go on forever baby?

It’s the not knowing that’s killing me

Will this program ever let me be?

I feel like such a fool

Is this undecidable?

I’ve got a halting problem, baby

They say there’s just no algorithm, baby

Will I ever rest again, oh baby?

Ooooooh I’m a machine

And that’s what’s killing me

Will this program ever let me be

A turing machine

Is this undecidable?

I’ve got a halting problem, baby

Well you know I’m just a machine

So you’d hope one day I’d learn

Well you know I’m just I’m just a machine

But still it burns

I’ve got a halting problem, baby