We define a notion of degree of unsolvability for subsets of R^n (where R is a real closed Archimedean field) and prove that, in contrast to Type 2 computability, the presence of exact equality in the BSS model forces exactly one jump of the unsolvability degree of decidable sets.
Equality is a jump / P. Boldi, S. Vigna. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 219:1-2(1999), pp. 49-64.
Equality is a jump
P. BoldiPrimo
;S. VignaUltimo
1999
Abstract
We define a notion of degree of unsolvability for subsets of R^n (where R is a real closed Archimedean field) and prove that, in contrast to Type 2 computability, the presence of exact equality in the BSS model forces exactly one jump of the unsolvability degree of decidable sets.File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.