No Cover Image

Book chapter 583 views

Symmetric Transrationals: The Data Type and the Algorithmic Degree of its Equational Theory

Jan A. Bergstra, John Tucker Orcid Logo

Lecture Notes in Computer Science, Volume: Lecture Notes in Computer Science 13560, Pages: 63 - 80

Swansea University Author: John Tucker Orcid Logo

Full text not available from this repository: check for access using links below.

Check full text

DOI (Published version): 10.1007/978-3-031-15629-8_4

Abstract

We introduce and investigate an arithmetical data typedesigned for computation with rational numbers. Called the symmetrictransrationals, this data type comes about as a more algebraicallysymmetric modification of the arithmetical data type of transrationalnumbers [9], which was inspired by the tran...

Full description

Published in: Lecture Notes in Computer Science
ISBN: 9783031156281 9783031156298
ISSN: 0302-9743 1611-3349
Published: Cham Springer Nature Switzerland 2022
Online Access: Check full text

URI: https://cronfa.swan.ac.uk/Record/cronfa61535
Tags: Add Tag
No Tags, Be the first to tag this record!
first_indexed 2022-10-11T20:53:07Z
last_indexed 2023-01-13T19:22:20Z
id cronfa61535
recordtype SURis
fullrecord <?xml version="1.0"?><rfc1807><datestamp>2022-10-27T13:07:21.4867332</datestamp><bib-version>v2</bib-version><id>61535</id><entry>2022-10-11</entry><title>Symmetric Transrationals: The Data Type and&#xA0;the&#xA0;Algorithmic Degree of&#xA0;its Equational Theory</title><swanseaauthors><author><sid>431b3060563ed44cc68c7056ece2f85e</sid><ORCID>0000-0003-4689-8760</ORCID><firstname>John</firstname><surname>Tucker</surname><name>John Tucker</name><active>true</active><ethesisStudent>false</ethesisStudent></author></swanseaauthors><date>2022-10-11</date><deptcode>SCS</deptcode><abstract>We introduce and investigate an arithmetical data typedesigned for computation with rational numbers. Called the symmetrictransrationals, this data type comes about as a more algebraicallysymmetric modification of the arithmetical data type of transrationalnumbers [9], which was inspired by the transreals of Anderson et.al. [1].We also define a bounded version of the symmetric transrationals therebymodelling some further key semantic properties of floating point arithmetic.We prove that the bounded symmetric transrationals constitutea data type. Next, we consider the equational theory and prove thatdeciding the validity of equations over the symmetric transrationals is1-1 algorithmically equivalent with deciding unsolvability of Diophantineequations over the rational numbers, which is a longstanding openproblem. The algorithmic degree of the bounded case remains open.</abstract><type>Book chapter</type><journal>Lecture Notes in Computer Science</journal><volume>Lecture Notes in Computer Science 13560</volume><journalNumber/><paginationStart>63</paginationStart><paginationEnd>80</paginationEnd><publisher>Springer Nature Switzerland</publisher><placeOfPublication>Cham</placeOfPublication><isbnPrint>9783031156281</isbnPrint><isbnElectronic>9783031156298</isbnElectronic><issnPrint>0302-9743</issnPrint><issnElectronic>1611-3349</issnElectronic><keywords>rational numbers, data types , computer arithmetic, common meadows, transrationals, diophantine problem, floating-point</keywords><publishedDay>7</publishedDay><publishedMonth>9</publishedMonth><publishedYear>2022</publishedYear><publishedDate>2022-09-07</publishedDate><doi>10.1007/978-3-031-15629-8_4</doi><url/><notes/><college>COLLEGE NANME</college><department>Computer Science</department><CollegeCode>COLLEGE CODE</CollegeCode><DepartmentCode>SCS</DepartmentCode><institution>Swansea University</institution><apcterm>Not Required</apcterm><funders/><projectreference/><lastEdited>2022-10-27T13:07:21.4867332</lastEdited><Created>2022-10-11T21:37:00.1476014</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>Jan A.</firstname><surname>Bergstra</surname><order>1</order></author><author><firstname>John</firstname><surname>Tucker</surname><orcid>0000-0003-4689-8760</orcid><order>2</order></author></authors><documents/><OutputDurs/></rfc1807>
spelling 2022-10-27T13:07:21.4867332 v2 61535 2022-10-11 Symmetric Transrationals: The Data Type and the Algorithmic Degree of its Equational Theory 431b3060563ed44cc68c7056ece2f85e 0000-0003-4689-8760 John Tucker John Tucker true false 2022-10-11 SCS We introduce and investigate an arithmetical data typedesigned for computation with rational numbers. Called the symmetrictransrationals, this data type comes about as a more algebraicallysymmetric modification of the arithmetical data type of transrationalnumbers [9], which was inspired by the transreals of Anderson et.al. [1].We also define a bounded version of the symmetric transrationals therebymodelling some further key semantic properties of floating point arithmetic.We prove that the bounded symmetric transrationals constitutea data type. Next, we consider the equational theory and prove thatdeciding the validity of equations over the symmetric transrationals is1-1 algorithmically equivalent with deciding unsolvability of Diophantineequations over the rational numbers, which is a longstanding openproblem. The algorithmic degree of the bounded case remains open. Book chapter Lecture Notes in Computer Science Lecture Notes in Computer Science 13560 63 80 Springer Nature Switzerland Cham 9783031156281 9783031156298 0302-9743 1611-3349 rational numbers, data types , computer arithmetic, common meadows, transrationals, diophantine problem, floating-point 7 9 2022 2022-09-07 10.1007/978-3-031-15629-8_4 COLLEGE NANME Computer Science COLLEGE CODE SCS Swansea University Not Required 2022-10-27T13:07:21.4867332 2022-10-11T21:37:00.1476014 Faculty of Science and Engineering School of Mathematics and Computer Science - Computer Science Jan A. Bergstra 1 John Tucker 0000-0003-4689-8760 2
title Symmetric Transrationals: The Data Type and the Algorithmic Degree of its Equational Theory
spellingShingle Symmetric Transrationals: The Data Type and the Algorithmic Degree of its Equational Theory
John Tucker
title_short Symmetric Transrationals: The Data Type and the Algorithmic Degree of its Equational Theory
title_full Symmetric Transrationals: The Data Type and the Algorithmic Degree of its Equational Theory
title_fullStr Symmetric Transrationals: The Data Type and the Algorithmic Degree of its Equational Theory
title_full_unstemmed Symmetric Transrationals: The Data Type and the Algorithmic Degree of its Equational Theory
title_sort Symmetric Transrationals: The Data Type and the Algorithmic Degree of its Equational Theory
author_id_str_mv 431b3060563ed44cc68c7056ece2f85e
author_id_fullname_str_mv 431b3060563ed44cc68c7056ece2f85e_***_John Tucker
author John Tucker
author2 Jan A. Bergstra
John Tucker
format Book chapter
container_title Lecture Notes in Computer Science
container_volume Lecture Notes in Computer Science 13560
container_start_page 63
publishDate 2022
institution Swansea University
isbn 9783031156281
9783031156298
issn 0302-9743
1611-3349
doi_str_mv 10.1007/978-3-031-15629-8_4
publisher Springer Nature Switzerland
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 0
active_str 0
description We introduce and investigate an arithmetical data typedesigned for computation with rational numbers. Called the symmetrictransrationals, this data type comes about as a more algebraicallysymmetric modification of the arithmetical data type of transrationalnumbers [9], which was inspired by the transreals of Anderson et.al. [1].We also define a bounded version of the symmetric transrationals therebymodelling some further key semantic properties of floating point arithmetic.We prove that the bounded symmetric transrationals constitutea data type. Next, we consider the equational theory and prove thatdeciding the validity of equations over the symmetric transrationals is1-1 algorithmically equivalent with deciding unsolvability of Diophantineequations over the rational numbers, which is a longstanding openproblem. The algorithmic degree of the bounded case remains open.
published_date 2022-09-07T04:20:25Z
_version_ 1763754351820537856
score 11.035634

Similar Items