> a given arbitrary program and input
Keyword emphasis mine.
That one little word that changes everything in how you interpret the statement.