Liner Notes

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 f and input i, a Turing machine that calculates f will, if fed the input i, halt on the output f(i) in the event that such an output exists (i.e. if f is defined for input i).

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.


Lyrics

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