No Cover Image

Journal article 553 views 34 downloads

Safe Recursive Set Functions / Arnold, Beckmann

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

Swansea University Author: Arnold, Beckmann

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 2018-02-09T04:57:17Z
id cronfa20591
recordtype SURis
fullrecord <?xml version="1.0"?><rfc1807><datestamp>2017-09-05T22:27:47.2944739</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&amp;apos;s J-hierarchy, relativised to the transitive closure of the function&amp;apos;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/><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></notes><college>COLLEGE NANME</college><department>Computer Science</department><CollegeCode>COLLEGE CODE</CollegeCode><DepartmentCode>SCS</DepartmentCode><institution>Swansea University</institution><lastEdited>2017-09-05T22:27:47.2944739</lastEdited><Created>2015-04-01T09:15:28.8947750</Created><path><level id="1">College of Science</level><level id="2">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><action/><embargoDate>2016-07-22T00:00:00.0000000</embargoDate><documentNotes/><copyrightCorrect>false</copyrightCorrect></document></documents></rfc1807>
spelling 2017-09-05T22:27:47.2944739 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&apos;s J-hierarchy, relativised to the transitive closure of the function&apos;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 2017-09-05T22:27:47.2944739 2015-04-01T09:15:28.8947750 College of 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
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 College of Science
hierarchytype
hierarchy_top_id collegeofscience
hierarchy_top_title College of Science
hierarchy_parent_id collegeofscience
hierarchy_parent_title College of Science
department_str Computer Science{{{_:::_}}}College of 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&apos;s J-hierarchy, relativised to the transitive closure of the function&apos;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-22T19:53:16Z
_version_ 1663069215041519616
score 10.892022