> a given arbitrary program and input

Keyword emphasis mine.

That one little word that changes everything in how you interpret the statement.