|
NeuroCOLT
Technical Report NC-TR-98-015
Equality
Is a Jump
Paolo Boldi & Sebastiano
Vigna
Dipartimento di Scienze dell'Informazione
Università degli Studi di Milano
Keywords:
perceptron, decision tree, maximal margin
Received:
08-JUN-98
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.
Download Compressed Postscript
|