{"entities":{"Q4934286":{"pageid":6963868,"ns":120,"title":"Item:Q4934286","lastrevid":108539396,"modified":"2026-11-06T21:57:57Z","type":"item","id":"Q4934286","labels":{},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1390021"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4934286$192F0750-1968-42DA-A250-68CC0762B20E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"01dca6b86c15e113848f2590cf6da041fdd77abc","datavalue":{"value":"0946.03054","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4934286$2D87AFAD-AC37-44C9-899B-C3334B1932A9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5f10e74d2799a0f84c55f8d253157b843029c56b","datavalue":{"value":{"entity-type":"item","numeric-id":926176,"id":"Q926176"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4934286$BA045E55-EF5A-4D4A-AEC4-252AA61541B2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1cbe6e62760c27153539f09b4f37f5e6a0a9487a","datavalue":{"value":{"time":"+2000-10-22T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q4934286$7BF37267-5FE2-4871-BD04-00FAC0F2E68D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"bacc42d4ab28169bcab125a394e2c486e425337a","datavalue":{"value":"03D75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4934286$731B46A8-E452-4FF2-83D9-65F14BDE9A1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"89663cdc2c9f64b2cd0a104bcac86329d89b9b2d","datavalue":{"value":"03-02","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4934286$C2D7BED5-7756-48AD-8F96-8F1D0F828D7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cde05172e5f9c37cef740a3519be6dc5014d282e","datavalue":{"value":"03D70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4934286$52F2B1A6-7424-4558-86F8-8D8FA3EC8537","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b064ee6228699e13db2d115cb3d92651e7073963","datavalue":{"value":"1390021","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4934286$2C6BE48C-CEFD-464D-B2E0-1A163C3A41B9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8e10916b80b773755913495cf6300d1fb3190a51","datavalue":{"value":"first-order structures","type":"string"},"datatype":"string"},"type":"statement","id":"Q4934286$2DA21A4E-A8F5-4E48-9386-FFEB59D94515","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"931e7c2f8692bdb4892e6d09801ada0fb0de3fc4","datavalue":{"value":"functional structures","type":"string"},"datatype":"string"},"type":"statement","id":"Q4934286$5796790F-742D-47BA-A7E9-0AD4CBE424A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"356b046535df57c7fda774f1d29a4f6c235f5a6f","datavalue":{"value":"unlimited register machines over functional structures","type":"string"},"datatype":"string"},"type":"statement","id":"Q4934286$EC0A2E33-0B44-4493-B94E-17AF23562CEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0f796ed2b460346bbba92264dac0da22a5120d5d","datavalue":{"value":"recursion","type":"string"},"datatype":"string"},"type":"statement","id":"Q4934286$989F470E-D913-46ED-9824-B3471BD025FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"01182eb09af29d05f3f864892bbfdbf39a6c0213","datavalue":{"value":"partial recursive functions over functional structures","type":"string"},"datatype":"string"},"type":"statement","id":"Q4934286$40AFE5DD-BEE3-478A-9A78-2FE24618F5F4","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4934286$CB521E1B-1F2E-48D8-8B4F-9A748118C1C9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b1f6543ca1c1dc31cb0a912e74e8920347f8e9ee","datavalue":{"value":{"entity-type":"item","numeric-id":3734395,"id":"Q3734395"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f2df8d6287091d2132c8aa988168b0b89099f469","datavalue":{"value":{"amount":"+0.7845918536186218","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4934286$5D852B88-ACAA-4E89-B820-275E95419003","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a60c2dd8918bb25a786a09b7cd1c4b08941fd149","datavalue":{"value":{"entity-type":"item","numeric-id":1078561,"id":"Q1078561"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a3bb327642616bc0d9b72793b73efec7ff699ae0","datavalue":{"value":{"amount":"+0.7644939422607422","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4934286$5D8C28D5-33E5-4821-BCBD-EBDFE8E04405","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9d8d1c3cbfcb85586de9d2eb6b91522af645ea70","datavalue":{"value":{"entity-type":"item","numeric-id":4637218,"id":"Q4637218"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f5ad3dbdd8204494689a40d182052be3780e91df","datavalue":{"value":{"amount":"+0.762904703617096","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4934286$9BCDD70E-010F-4DB2-85FD-96B060B700D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d35690a008ddbe5c258080352d84a240981e2974","datavalue":{"value":{"entity-type":"item","numeric-id":3365454,"id":"Q3365454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0a94bb402d93c851f8404498c74dfcb9ba2aca59","datavalue":{"value":{"amount":"+0.7539180517196655","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4934286$CA916108-10A4-4316-8E72-8507D20A5E9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"16461d437e263daf995ab78d470c490220a8fdbe","datavalue":{"value":{"entity-type":"item","numeric-id":3980817,"id":"Q3980817"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"51350a80fe1bb8fda678e0550da40cb451d43f25","datavalue":{"value":{"amount":"+0.7417402267456055","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4934286$FB80F616-E752-456B-9ADB-1F9AEFCB69CF","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"dfc2f7ed97a89f44e05bb64ae2dc43164bf5f9fe","datavalue":{"value":"While recursion theory traditionally deals with number-theoretic relations and functions, the present essay offers a survey of recursion theory on abstract structures (ART henceforth). ART has its roots in various attempts of the late fifties and early sixties of generalizing the theory of partial recursive functions to higher types (Kleene), to ordinals and sets (Takeuti, Kripke, Platek). The backbone of Hinman's chapter is provided by a basic conceptual distinction with its technical implementations: either one generalizes recursion theory by seeking for abstract machine models, or else one regards ART as a sort of special definability theory for abstract structures. According to the first option, abstract machines have been introduced over the years in different contexts -- ranging from the functionals of finite type over natural numbers to rings and abstract algebras -- by several authors (Kleene, Friedman, Moldestad, Stoltenberg-Hansen, Tucker, Zucker, Blum, Shub, Smale). In section 3, the reader can find Hinman's proposal: a natural abstract version of unlimited register machines over first-order structures; register machines immediately provide the class \\(\\text{Reg}(\\mathcal{A})\\) of the partial functionals (maps applicable to elements of the structure domain as well as to partial maps from \\(A\\) to \\(A\\)), which are \\(\\text{UMR}(\\mathcal{A})\\)-computable, i.e., computable by an unlimited register machine program over a first-order structure \\(\\mathcal{A}\\). \\(\\text{Reg}(\\mathcal{A})\\) has natural closure properties (e.g., closure under explicit definability) and it coincides with standard computability over natural numbers. However, a problem with \\(\\text{UMR}(\\mathcal{A})\\)-computability is that it is not strong enough in general; in order to get more sophisticated recursion-theoretic results (e.g., an abstract analogue of the first recursion theorem of Kleene, selection theorems), one must have a copy of the natural numbers as a built-in facility of the given structure. This limitation suggests to consider the second, more powerful option (section 4), which is mainly inspired by the investigations of the late sixties and the seventies, when it was shown that various forms of generalized recursion theory can be subsumed under inductive definability. Roughly, the essence of this approach lies in the fact that the relevant recursive objects (the semicomputable sets, the computable functions or functionals) on a structure \\(\\mathcal{A}\\) can be characterized by means of (suitably general versions of) the least fixed point operator Rec (typically, if \\(F\\) is a partial monotone functional, i.e., one preserving inclusion between partial maps \\(f\\) : \\(A\\rightarrow A\\), \\(\\text{Rec}(F)\\) will be the least partial function \\(g\\) solving the equation \\(g\\simeq F(g)\\); \\(g\\) is obtained by (possibly) transfinite iteration of \\(F\\)). Clearly, in contrast to \\(\\text{UMR}(\\mathcal{A})\\)-computability, this approach is inherently second-order, and its generalization to abstract structures requires abstract functional structures, namely first-order structures expanded by means of monotone functionals. Following Platek's idea of internalizing the least fixed point construction, and refinements due to Moschovakis and Kechris, Hinman introduces the class \\(\\text{Rec}(\\mathcal{A})\\) of \\(\\mathcal{A}\\)-recursive functionals over a given functional structure \\(\\mathcal{A}\\) as the least class of functionals which is closed under explicit definition, substitution and the (simultaneous) recursion operator Rec. The new class is closed under explicit definition and it enjoys a normal-form theorem: every \\(\\mathcal{A}\\)-recursive functional can be obtained from a finite sequence of explicitly definable functionals by a single application of the fixed point operator Rec. As a corollary, \\(\\text{Rec}(\\mathcal{A})\\) can be naturally indexed and it is possible to prove that register machine computable functionals are \\(\\mathcal{A}\\)-recursive. That the proposed abstract recursion theories are non-empty and well-behaved, is ensured by a number of applications which are discussed in section 5 (ordinal recursion over admissible ordinals, positive elementary inductive definability over abstract structures, recursion on the finite type structure over a functional structure). It is also shown that \\(\\text{Reg}(\\mathcal{A})\\) -- and hence \\(\\text{Rec}(\\mathcal{A})\\) -- is powerful enough to subsume BSS-computability (computability in the sense of Blum, Shub, Smale) over arbitrary commutative ordered rings with unit. Section 6 is especially interesting, as it deals with the problem of generalizing recursion-theoretic results which depend on the existence of an effective indexing for the computable functionals and require first-order structures \\(\\mathcal{A}\\) with arithmetic (those comprising an isomorphic copy of the structure of natural numbers with successor, number-theoretic identity and zero). However, this is not enough. For instance, assume that we want to show that the partial function \\(U(b,a) \\simeq \\{ b \\}(a)\\) is \\(\\text{UMR}(\\mathcal{A})\\) -computable. In the standard number-theoretic case, one heavily rely on the fact that the content of finitely many registers can be encoded as one element of the underlying structure; but this is in general impossible for first-order structures with arithmetic. It is shown that the difficulty is avoided if the given structure \\(\\mathcal{A}\\) admits term evaluation, i.e., for each \\(k\\), the evaluation for terms (in the language of \\(\\mathcal{A}\\)) with at most \\(k\\) free variables under an assignement \\(a\\) in \\(\\mathcal{A}\\) is a computable function \\(F_k(gn(t),a)\\) of \\(\\text{Reg}(\\mathcal{A})\\) (\\(gn(t)\\) encodes the term \\(t\\)). As a major application, it turns out that \\(\\text{Rec}(\\mathcal{A})\\) coincides with \\(\\text{Reg}(\\mathcal{A})\\), whenever \\(\\mathcal{A}\\) is a first-order structure with arithmetic and term evalutation (e.g., this holds if \\(\\mathcal{A}\\) is a commutative ordered ring with unit). \\text{Sec}tion 7 deals with the structural properties of sections and envelopes (given \\(\\mathcal{A}\\), a relation \\(R\\) is in \\(\\text{Sec}_{\\text{Reg}}(\\mathcal{A})\\) (\\(\\text{Sec}_{\\text{Rec}}(\\mathcal{A})\\)) iff its characteristic function is in \\(\\text{Reg}(\\mathcal{A})\\) (\\(\\text{Rec}(\\mathcal{A})\\)); \\(R\\) is in \\(\\text{Env}_{\\text{Reg}}(\\mathcal{A})\\) (\\(\\text{Env}_{\\text{Rec}}(\\mathcal{A})\\)) iff \\(R\\) is the domain of some \\(F \\in \\text{Reg}(\\mathcal{A})\\) (\\(\\text{Rec}(\\mathcal{A})\\)). The typical results establish generalizations of well-known properties of recursive and semi-recursive sets of natural numbers (e.g, if \\(\\mathcal{A}\\) is first-order with arithmetic, \\(R\\) is in \\(\\text{Sec}_{\\text{Reg}}(\\mathcal{A})\\) iff \\(R\\) and its complement are in \\(\\text{Env}_{\\text{Reg}}(\\mathcal{A})\\)). It also holds that a relation is in \\(\\text{Env}_{\\text{Reg}}(\\mathcal{A})\\) iff it is a countable union of relations which are quantifier-free definable over \\(\\mathcal{A}\\) (this fact has interesting specializations to the case of BSS-computability over the reals). As to \\(\\text{Rec}(\\mathcal{A})\\), the highlight is an abstract version of the so-called stage comparison theorem, under a suitable additional technical constraint (\\(\\mathcal{A}\\) is normal). In conclusion, Hinman's chapter provides a neat introduction to a rich area, which could profitably interact with present-day research issues (is it possible to improve the applications of ART to structures arising from computer science, to algebraic structures and analysis?). The historically minded reader, with some background in generalized recursion theory, could also reconsider \\textit{G. Kreisel's} essay ``Some reasons for generalizing recursion theory'' [in: R. Gandy , C. M. Yates (eds.), Logic Colloquium '69, Stud. Log. Found. Math. 61, North Holland, Amsterdam, 139-198 (1971; Zbl 0219.02027)] in order to get a flavour of the original technical and conceptual motivations for extending recursion theory, and compare them with present-day motivations. {A typo: p. \\(348^{15}\\)}. For the entire collection see [Zbl 0923.03001].","type":"string"},"datatype":"string"},"type":"statement","id":"Q4934286$D701D3B6-3619-4EF8-99C3-1F8AEFA069DD","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:4934286","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:4934286"}}}}}