Content deleted Content added
partial alpha-recursive functions are typically partial functions from alpha to itself, not total functions. If it is total, then it is already alpha-recursive |
moved previous edit slightly for better ease of reading (and added link to partial functions webpage) |
||
Line 8:
There are also some similar definitions for functions mapping <math>\alpha</math> to <math>\alpha</math>:<ref name="relconstr">Srebrny, Marian, [http://matwbn.icm.edu.pl/ksiazki/fm/fm96/fm96114.pdf Relatively constructible transitive models] (1975, p.165). Accessed 21 October 2021.</ref>
*A [[partial function]] from <math>\alpha</math> to <math>\alpha</math> is '''<math>\alpha</math>-recursively-enumerable''', or '''<math>\alpha</math>-partial recursive''',<ref>W. Richter, P. Aczel, "[https://www.duo.uio.no/bitstream/handle/10852/44063/1973-13.pdf Inductive Definitions and Reflecting Properties of Admissible Ordinals]" (1974), p.30. Accessed 7 February 2023.</ref> iff its graph is <math>\Sigma_1</math>-definable on <math>(L_\alpha,\in)</math>
*A partial function from <math>\alpha</math> to <math>\alpha</math> is '''<math>\alpha</math>-recursive''' iff its graph is <math>\Delta_1</math>-definable on <math>(L_\alpha,\in)</math>. Like in the case of classical recursion theory, any ''total'' <math>\alpha</math>-recursively-enumerable function <math>f:\alpha\rightarrow\alpha</math> is <math>\alpha</math>-recursive.
*Additionally, a partial function from <math>\alpha</math> to <math>\alpha</math> is '''<math>\alpha</math>-arithmetical''' iff there exists some <math>n\in\omega</math> such that the function's graph is <math>\Sigma_n</math>-definable on <math>(L_\alpha,\in)</math>.
| |||