User:IssaRice/Computability and logic/Least search operator: Difference between revisions
No edit summary |
|||
| Line 1: | Line 1: | ||
The '''least search operator''', '''minimzation operator''', or '''μ-operator''' is used in computability theory to define new functions. | The '''least search operator''', '''minimzation operator''', or '''μ-operator''' is used in computability theory to define new functions. | ||
The least search operator allows us to move from primitive recursive functions to general recursive functions. | The least search operator allows us to move from primitive recursive functions to general recursive (total or partial) functions. | ||
==Definition== | ==Definition== | ||
Latest revision as of 05:07, 21 December 2018
The least search operator, minimzation operator, or μ-operator is used in computability theory to define new functions.
The least search operator allows us to move from primitive recursive functions to general recursive (total or partial) functions.
Definition
- note: the least search operator may run into an "infinite loop". This means that partial recursive functions are not in general total.
Notation
Most texts seem to write the least search operator was as in or maybe (like the operator for defining anonymous functions).
![{\displaystyle \mu y[f(y)=0]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/098e52871e5fd3db7a0692b0e622bfd378530825)
Boolos/Burgess/Jeffrey use (for "minimization").
Intuition
bounded search vs unbounded search; bounded for-loop vs while-loop.