No Cover Image

Book chapter 568 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.

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!
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.
Keywords: rational numbers, data types , computer arithmetic, common meadows, transrationals, diophantine problem, floating-point
College: Faculty of Science and Engineering
Start Page: 63
End Page: 80