Skip to main content
replaced http://mathoverflow.net/ with https://mathoverflow.net/
Source Link

(This is more of a comment than an answer, but it's a bit too long to be split into comments so I'll post it as an answer.)

I don't know about functions defined on an arbitrary admissible set, but at least for admissible levels of the constructible hierarchy, you might be interested in what are called "$(\infty,0)$-recursive functions" in chapter VIII ("Recursion on Ordinals") of Peter G. Hinman's book Recursion-Theoretic Hierarchies (1978, available here), and also on this related questionthis related question I asked a while ago while trying to make sense (without much success) of the various definitions. Hinman writes (op.cit., p.378) that:

The $(\infty,0)$-recursive functions will play somewhat the role here of the primitive recursive functions of ordinary recursion theory.

Perhaps even more relevant to your question would be the $(\infty,\lambda)$-recursive functions in Hinman's terminology, or even more the primitive $(\infty,\lambda)$-recursive functions in the terminology of the question I linked to, where $\lambda$ is the height of the admissible set considered (at least for a $L_\lambda$). But as I noted, the precise relation between these concepts escapes me.

Also somewhat relevant to your question might be Stephen G. Simpson's paper titled "Short Course on Admissible Recursion Theory" on p. 355–390 of Fenstad, Gandy & Sacks (eds.), Generalized Recursion Theory II (1978), proceedings of a symposium held in Oslo in 1977. It contains the clearest (if terse) explanation I found so far of how primitive recursive ordinal functions are defined and how they relate to more general recursion on ordinals.

(This is more of a comment than an answer, but it's a bit too long to be split into comments so I'll post it as an answer.)

I don't know about functions defined on an arbitrary admissible set, but at least for admissible levels of the constructible hierarchy, you might be interested in what are called "$(\infty,0)$-recursive functions" in chapter VIII ("Recursion on Ordinals") of Peter G. Hinman's book Recursion-Theoretic Hierarchies (1978, available here), and also on this related question I asked a while ago while trying to make sense (without much success) of the various definitions. Hinman writes (op.cit., p.378) that:

The $(\infty,0)$-recursive functions will play somewhat the role here of the primitive recursive functions of ordinary recursion theory.

Perhaps even more relevant to your question would be the $(\infty,\lambda)$-recursive functions in Hinman's terminology, or even more the primitive $(\infty,\lambda)$-recursive functions in the terminology of the question I linked to, where $\lambda$ is the height of the admissible set considered (at least for a $L_\lambda$). But as I noted, the precise relation between these concepts escapes me.

Also somewhat relevant to your question might be Stephen G. Simpson's paper titled "Short Course on Admissible Recursion Theory" on p. 355–390 of Fenstad, Gandy & Sacks (eds.), Generalized Recursion Theory II (1978), proceedings of a symposium held in Oslo in 1977. It contains the clearest (if terse) explanation I found so far of how primitive recursive ordinal functions are defined and how they relate to more general recursion on ordinals.

(This is more of a comment than an answer, but it's a bit too long to be split into comments so I'll post it as an answer.)

I don't know about functions defined on an arbitrary admissible set, but at least for admissible levels of the constructible hierarchy, you might be interested in what are called "$(\infty,0)$-recursive functions" in chapter VIII ("Recursion on Ordinals") of Peter G. Hinman's book Recursion-Theoretic Hierarchies (1978, available here), and also on this related question I asked a while ago while trying to make sense (without much success) of the various definitions. Hinman writes (op.cit., p.378) that:

The $(\infty,0)$-recursive functions will play somewhat the role here of the primitive recursive functions of ordinary recursion theory.

Perhaps even more relevant to your question would be the $(\infty,\lambda)$-recursive functions in Hinman's terminology, or even more the primitive $(\infty,\lambda)$-recursive functions in the terminology of the question I linked to, where $\lambda$ is the height of the admissible set considered (at least for a $L_\lambda$). But as I noted, the precise relation between these concepts escapes me.

Also somewhat relevant to your question might be Stephen G. Simpson's paper titled "Short Course on Admissible Recursion Theory" on p. 355–390 of Fenstad, Gandy & Sacks (eds.), Generalized Recursion Theory II (1978), proceedings of a symposium held in Oslo in 1977. It contains the clearest (if terse) explanation I found so far of how primitive recursive ordinal functions are defined and how they relate to more general recursion on ordinals.

slightly expand comment (try to explain what I think is relevant)
Source Link
Gro-Tsen
  • 32.5k
  • 5
  • 88
  • 375

(This is more of a comment than an answer, but it's a bit too long to be split into comments so I'll post it as an answer.)

I don't know about functions defined on an arbitrary admissible set, but at least for admissible levels of the constructible hierarchy, you might be interested in what are called "$(\infty,0)$-recursive functions" in chapter VIII ("Recursion on Ordinals") of Peter G. Hinman's book Recursion-Theoretic Hierarchies (1978, available here), and also on this related question I asked a while ago while trying to make sense (without much success) of the various definitions. Hinman writes (op.cit., p.378) that:

The $(\infty,0)$-recursive functions will play somewhat the role here of the primitive recursive functions of ordinary recursion theory.

Perhaps even more relevant to your question would be the $(\infty,\lambda)$-recursive functions in Hinman's terminology, or even more the primitive $(\infty,\lambda)$-recursive functions in the terminology of the question I linked to, where $\lambda$ is the height of the admissible set considered (at least for a $L_\lambda$). But as I noted, the precise relation between these concepts escapes me.

Also somewhat relevant to your question might be Stephen G. Simpson's paper titled "Short Course on Admissible Recursion Theory" on p. 355–390 of Fenstad, Gandy & Sacks (eds.), Generalized Recursion Theory II (1978), proceedings of a symposium held in Oslo in 1977. It contains the clearest (if terse) explanation I found so far of how primitive recursive ordinal functions are defined and how they relate to more general recursion on ordinals.

(This is more of a comment than an answer, but it's a bit too long to be split into comments so I'll post it as an answer.)

I don't know about functions defined on an arbitrary admissible set, but at least for admissible levels of the constructible hierarchy, you might be interested in what are called "$(\infty,0)$-recursive functions" in chapter VIII ("Recursion on Ordinals") of Peter G. Hinman's book Recursion-Theoretic Hierarchies (1978, available here), and also on this related question I asked a while ago while trying to make sense (without much success) of the various definitions. Hinman writes (op.cit., p.378) that:

The $(\infty,0)$-recursive functions will play somewhat the role here of the primitive recursive functions of ordinary recursion theory.

Also somewhat relevant to your question might be Stephen G. Simpson's paper titled "Short Course on Admissible Recursion Theory" on p. 355–390 of Fenstad, Gandy & Sacks (eds.), Generalized Recursion Theory II (1978), proceedings of a symposium held in Oslo in 1977.

(This is more of a comment than an answer, but it's a bit too long to be split into comments so I'll post it as an answer.)

I don't know about functions defined on an arbitrary admissible set, but at least for admissible levels of the constructible hierarchy, you might be interested in what are called "$(\infty,0)$-recursive functions" in chapter VIII ("Recursion on Ordinals") of Peter G. Hinman's book Recursion-Theoretic Hierarchies (1978, available here), and also on this related question I asked a while ago while trying to make sense (without much success) of the various definitions. Hinman writes (op.cit., p.378) that:

The $(\infty,0)$-recursive functions will play somewhat the role here of the primitive recursive functions of ordinary recursion theory.

Perhaps even more relevant to your question would be the $(\infty,\lambda)$-recursive functions in Hinman's terminology, or even more the primitive $(\infty,\lambda)$-recursive functions in the terminology of the question I linked to, where $\lambda$ is the height of the admissible set considered (at least for a $L_\lambda$). But as I noted, the precise relation between these concepts escapes me.

Also somewhat relevant to your question might be Stephen G. Simpson's paper titled "Short Course on Admissible Recursion Theory" on p. 355–390 of Fenstad, Gandy & Sacks (eds.), Generalized Recursion Theory II (1978), proceedings of a symposium held in Oslo in 1977. It contains the clearest (if terse) explanation I found so far of how primitive recursive ordinal functions are defined and how they relate to more general recursion on ordinals.

Source Link
Gro-Tsen
  • 32.5k
  • 5
  • 88
  • 375

(This is more of a comment than an answer, but it's a bit too long to be split into comments so I'll post it as an answer.)

I don't know about functions defined on an arbitrary admissible set, but at least for admissible levels of the constructible hierarchy, you might be interested in what are called "$(\infty,0)$-recursive functions" in chapter VIII ("Recursion on Ordinals") of Peter G. Hinman's book Recursion-Theoretic Hierarchies (1978, available here), and also on this related question I asked a while ago while trying to make sense (without much success) of the various definitions. Hinman writes (op.cit., p.378) that:

The $(\infty,0)$-recursive functions will play somewhat the role here of the primitive recursive functions of ordinary recursion theory.

Also somewhat relevant to your question might be Stephen G. Simpson's paper titled "Short Course on Admissible Recursion Theory" on p. 355–390 of Fenstad, Gandy & Sacks (eds.), Generalized Recursion Theory II (1978), proceedings of a symposium held in Oslo in 1977.