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