No Cover Image

Journal article 1371 views 218 downloads

Safe Recursive Set Functions

Arnold Beckmann Orcid Logo, Samuel R. Buss, Sy-David Friedman

The Journal of Symbolic Logic, Volume: 80, Issue: 03, Pages: 730 - 762

Swansea University Author: Arnold Beckmann Orcid Logo

DOI (Published version): 10.1017/jsl.2015.26

Abstract

This paper introduces the safe recursive set functions based on a Bellantoni-Cook style subclass of the primitive recursive set functions. It shows that the functions computed by safe recursive set functions under a list encoding of finite strings by hereditarily finite sets are exactly the polynomi...

Full description

Published in: The Journal of Symbolic Logic
Published: 2015
URI: https://cronfa.swan.ac.uk/Record/cronfa20591
Tags: Add Tag
No Tags, Be the first to tag this record!
first_indexed 2015-04-02T02:05:34Z
last_indexed 2021-01-29T03:35:03Z
id cronfa20591
recordtype SURis
fullrecord <?xml version="1.0"?><rfc1807><datestamp>2021-01-28T13:04:54.2602982</datestamp><bib-version>v2</bib-version><id>20591</id><entry>2015-04-01</entry><title>Safe Recursive Set Functions</title><swanseaauthors><author><sid>1439ebd690110a50a797b7ec78cca600</sid><ORCID>0000-0001-7958-5790</ORCID><firstname>Arnold</firstname><surname>Beckmann</surname><name>Arnold Beckmann</name><active>true</active><ethesisStudent>false</ethesisStudent></author></swanseaauthors><date>2015-04-01</date><deptcode>SCS</deptcode><abstract>This paper introduces the safe recursive set functions based on a Bellantoni-Cook style subclass of the primitive recursive set functions. It shows that the functions computed by safe recursive set functions under a list encoding of finite strings by hereditarily finite sets are exactly the polynomial growth rate functions computed by alternating exponential time Turing machines with polynomially many alternations. It also shows that the functions computed by safe recursive set functions under a more efficient binary tree encoding of finite strings by hereditarily finite sets are exactly the quasipolynomial growth rate functions computed by alternating quasipolynomial time Turing machines with polylogarithmic many alternations. The safe recursive set functions are characterized on arbitrary sets in definability-theoretic terms. In its strongest form, it is shown that a function on arbitrary sets is safe recursive if, and only if, it is uniformly definable in some polynomial level of a refinement of Jensen's J-hierarchy, relativised to the transitive closure of the function's arguments. An observation is that safe-recursive functions on infinite binary strings are equivalent to functions computed by so-called infinite-time Turing machines in time less than &#x3C9;&#x3C9;. Finally a machine model is given for safe recursion which is based on set-indexed parallel processors and the natural bound on running times.</abstract><type>Journal Article</type><journal>The Journal of Symbolic Logic</journal><volume>80</volume><journalNumber>03</journalNumber><paginationStart>730</paginationStart><paginationEnd>762</paginationEnd><publisher/><placeOfPublication/><isbnPrint/><isbnElectronic/><issnPrint/><issnElectronic/><keywords>Safe recursive, set functions, alternating Turing machines, infinite time Turing machines, polynomial time, rudimentary functions, Jensen hierarchy.</keywords><publishedDay>22</publishedDay><publishedMonth>7</publishedMonth><publishedYear>2015</publishedYear><publishedDate>2015-07-22</publishedDate><doi>10.1017/jsl.2015.26</doi><url/><notes/><college>COLLEGE NANME</college><department>Computer Science</department><CollegeCode>COLLEGE CODE</CollegeCode><DepartmentCode>SCS</DepartmentCode><institution>Swansea University</institution><apcterm/><lastEdited>2021-01-28T13:04:54.2602982</lastEdited><Created>2015-04-01T09:15:28.8947750</Created><path><level id="1">Faculty of Science and Engineering</level><level id="2">School of Mathematics and Computer Science - Computer Science</level></path><authors><author><firstname>Arnold</firstname><surname>Beckmann</surname><orcid>0000-0001-7958-5790</orcid><order>1</order></author><author><firstname>Samuel R.</firstname><surname>Buss</surname><order>2</order></author><author><firstname>Sy-David</firstname><surname>Friedman</surname><order>3</order></author></authors><documents><document><filename>0020591-07052015214543.pdf</filename><originalFilename>paper.pdf</originalFilename><uploaded>2015-05-07T21:45:43.2100000</uploaded><type>Output</type><contentLength>459674</contentLength><contentType>application/pdf</contentType><version>Accepted Manuscript</version><cronfaStatus>true</cronfaStatus><embargoDate>2016-07-22T00:00:00.0000000</embargoDate><copyrightCorrect>false</copyrightCorrect></document></documents><OutputDurs/></rfc1807>
spelling 2021-01-28T13:04:54.2602982 v2 20591 2015-04-01 Safe Recursive Set Functions 1439ebd690110a50a797b7ec78cca600 0000-0001-7958-5790 Arnold Beckmann Arnold Beckmann true false 2015-04-01 SCS This paper introduces the safe recursive set functions based on a Bellantoni-Cook style subclass of the primitive recursive set functions. It shows that the functions computed by safe recursive set functions under a list encoding of finite strings by hereditarily finite sets are exactly the polynomial growth rate functions computed by alternating exponential time Turing machines with polynomially many alternations. It also shows that the functions computed by safe recursive set functions under a more efficient binary tree encoding of finite strings by hereditarily finite sets are exactly the quasipolynomial growth rate functions computed by alternating quasipolynomial time Turing machines with polylogarithmic many alternations. The safe recursive set functions are characterized on arbitrary sets in definability-theoretic terms. In its strongest form, it is shown that a function on arbitrary sets is safe recursive if, and only if, it is uniformly definable in some polynomial level of a refinement of Jensen's J-hierarchy, relativised to the transitive closure of the function's arguments. An observation is that safe-recursive functions on infinite binary strings are equivalent to functions computed by so-called infinite-time Turing machines in time less than ωω. Finally a machine model is given for safe recursion which is based on set-indexed parallel processors and the natural bound on running times. Journal Article The Journal of Symbolic Logic 80 03 730 762 Safe recursive, set functions, alternating Turing machines, infinite time Turing machines, polynomial time, rudimentary functions, Jensen hierarchy. 22 7 2015 2015-07-22 10.1017/jsl.2015.26 COLLEGE NANME Computer Science COLLEGE CODE SCS Swansea University 2021-01-28T13:04:54.2602982 2015-04-01T09:15:28.8947750 Faculty of Science and Engineering School of Mathematics and Computer Science - Computer Science Arnold Beckmann 0000-0001-7958-5790 1 Samuel R. Buss 2 Sy-David Friedman 3 0020591-07052015214543.pdf paper.pdf 2015-05-07T21:45:43.2100000 Output 459674 application/pdf Accepted Manuscript true 2016-07-22T00:00:00.0000000 false
title Safe Recursive Set Functions
spellingShingle Safe Recursive Set Functions
Arnold Beckmann
title_short Safe Recursive Set Functions
title_full Safe Recursive Set Functions
title_fullStr Safe Recursive Set Functions
title_full_unstemmed Safe Recursive Set Functions
title_sort Safe Recursive Set Functions
author_id_str_mv 1439ebd690110a50a797b7ec78cca600
author_id_fullname_str_mv 1439ebd690110a50a797b7ec78cca600_***_Arnold Beckmann
author Arnold Beckmann
author2 Arnold Beckmann
Samuel R. Buss
Sy-David Friedman
format Journal article
container_title The Journal of Symbolic Logic
container_volume 80
container_issue 03
container_start_page 730
publishDate 2015
institution Swansea University
doi_str_mv 10.1017/jsl.2015.26
college_str Faculty of Science and Engineering
hierarchytype
hierarchy_top_id facultyofscienceandengineering
hierarchy_top_title Faculty of Science and Engineering
hierarchy_parent_id facultyofscienceandengineering
hierarchy_parent_title Faculty of Science and Engineering
department_str School of Mathematics and Computer Science - Computer Science{{{_:::_}}}Faculty of Science and Engineering{{{_:::_}}}School of Mathematics and Computer Science - Computer Science
document_store_str 1
active_str 0
description This paper introduces the safe recursive set functions based on a Bellantoni-Cook style subclass of the primitive recursive set functions. It shows that the functions computed by safe recursive set functions under a list encoding of finite strings by hereditarily finite sets are exactly the polynomial growth rate functions computed by alternating exponential time Turing machines with polynomially many alternations. It also shows that the functions computed by safe recursive set functions under a more efficient binary tree encoding of finite strings by hereditarily finite sets are exactly the quasipolynomial growth rate functions computed by alternating quasipolynomial time Turing machines with polylogarithmic many alternations. The safe recursive set functions are characterized on arbitrary sets in definability-theoretic terms. In its strongest form, it is shown that a function on arbitrary sets is safe recursive if, and only if, it is uniformly definable in some polynomial level of a refinement of Jensen's J-hierarchy, relativised to the transitive closure of the function's arguments. An observation is that safe-recursive functions on infinite binary strings are equivalent to functions computed by so-called infinite-time Turing machines in time less than ωω. Finally a machine model is given for safe recursion which is based on set-indexed parallel processors and the natural bound on running times.
published_date 2015-07-22T03:24:23Z
_version_ 1763750826459791360
score 11.037253

Similar Items