User:IssaRice/Computability and logic/Bounded computation trick: Difference between revisions
No edit summary |
No edit summary |
||
| (5 intermediate revisions by the same user not shown) | |||
| Line 3: | Line 3: | ||
Some examples of this trick in use: | Some examples of this trick in use: | ||
* the idea of dovetailing | |||
* showing that a recursively enumerable set is primitive-recursively enumerable | * showing that a recursively enumerable set is primitive-recursively enumerable | ||
* Kleene's T predicate and normal form | * 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 domain of an algorithm implies effectively enumerable (theorem 3.5) | ||
* Peter Smith's proof that K is recursively enumerable (theorem 3.8) | * Peter Smith's proof that K is recursively enumerable (theorem 3.8) | ||
* the | * the first 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 | |||
Latest revision as of 23:01, 24 March 2019
Instead of saying "compute this thing" you can say "compute this thing for steps", then let vary. This trick makes the computation bounded, which is useful in certain situations.
Some examples of this trick in use:
- the idea of dovetailing
- 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 first 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