Technical Report Series in Neural and Computational Learning

[john@dcs.rhbnc.ac.uk]

The European Community ESPRIT Working Group in Neural and Computational 
       Learning Theory (NeuroCOLT):

Many apologies that the previous technical report NC-TR-94-5 was not available
when first announced. It is now installed. I have also installed an ascii file
entitled `abstracts' which holds an up to date list of the Technical Reports
with their abstracts.

A new technical report is also now available:
---------------------------------------
NeuroCOLT Technical Report NC-TR-94-7:
---------------------------------------
On the power of real Turing machines over binary inputs
by Felipe Cucker, Universitat Pompeu Fabra, Balmes 132, Barcelona 08008, SPAIN
and Dima Grigoriev, Depts. of Comp. Science and Maths, Penn State University,
    University Park, PA 16802, USA

Abstract:

In recent years the study of the complexity of computational problems
involving real numbers has been an increasing research area.  Blum,
Shub and Smale (1989) proposed a computational model ---the real Turing
machine--- for dealing with the above problems was developed.

The aim of this paper is to prove that
$\BP(\PAR)=\;$PSPACE/{\it poly} where $\PAR$ is the class of sets
computed in parallel polynomial time by (ordinary) real Turing machines.
As a consequence we obtain the existence of binary sets that do not
belong to the
Boolean part of $\PAR$ (an extension of the result of Koiran (1994)
since $\PH\subseteq\PAR$) and a separation of complexity classes in
the real setting.

------------------------
The Report NC-TR-94-7 can be accessed and printed as follows (follow the same
procedure for getting the abstracts file)

% ftp cscx.cs.rhbnc.ac.uk  (134.219.200.45)
Name: anonymous
password: your full email address
ftp> cd pub/neurocolt/tech_reports
ftp> binary
ftp> get nc-tr-94-7.ps.Z
ftp> bye
% zcat nc-tr-94-7.ps.Z | lpr -l

Uncompressed versions of the postscript files have also been left for anyone not
having an uncompress facility.

Best wishes
John