Page "Chaitin's constant" Paragraph 8

The function F is called prefix-free if there are no two elements p, p ′ in its domain such that p ′ is a proper extension of p. This can be rephrased as: the domain of F is a prefix-free code ( instantaneous code ) on the set of finite binary strings.

A simple way to enforce prefix-free-ness is to use machines whose means of input is a binary stream from which bits can be read one at a time.

There is no end-of-stream marker ; the end of input is determined by when the universal machine decides to stop reading more bits.

Here, the difference between the two notions of program mentioned in the last paragraph becomes clear ; one is easily recognized by some grammar, while the other requires arbitrary computation to recognize.