User:IssaRice/Computability and logic/Bounded computation trick

Instead of saying "compute this thing" you can say "compute this thing for $n$ steps", then let $n$ vary. This trick makes the computation bounded, which is useful in certain situations.

Some examples of this trick in use:

• showing that a recursively enumerable set is primitive-recursively enumerable
• Kleene's T predicate and normal form
• Peter Smith's proof that domain of an algorithm implies effectively enumerable (theorem 3.5)
• Peter Smith's proof that K is recursively enumerable (theorem 3.8)
• the second graph principle
• goedel's beta function (this one is slightly different, i think)
• definition of Prf(m,n) in logic
• when arithmetizing syntax in logic (see e.g. Leary and Kristiansen), there's the need to find bounds for things to ensure the predicates are primitive recursive