<div dir="ltr">Dear all,<div><br></div><div>Next week our CS seminar series will host <span style="font-size:12.8px">Florian Steinberg (<a href="http://www.mathematik.tu-darmstadt.de/~steinberg/">http://www.mathematik.tu-darmstadt.de/~steinberg/</a>) who will give a talk titled "Introduction to second order complexity theory". The talk will be held in MB108 from 11am to 12.30am. </span><b style="font-size:12.8px">Please note the unusual place and time</b><span style="font-size:12.8px">.</span></div><div><span style="font-size:12.8px"><br></span></div><div><span style="font-size:12.8px">Best,</span></div><div><span style="font-size:12.8px">Luca</span></div><div><span style="font-size:12.8px"><br></span></div><div><span style="font-size:12.8px">Abstract:</span></div><div><span style="font-size:12.8px">Classical computability and complexity theory use Turing machines as a foundation for consideration of effectivity (computability) and efficiency (polynomial-time computability) of operations on countable discrete structures. For many applications in engineering it would be desirable to not only compute on countable discrete structures but also to compute on continuous structures like the real numbers. The most common model for computation on the real numbers by digital computers are floating point computations. Modeling real numbers by machine numbers is unsatisfactory from a mathematical point of view as the content of a proof of correctness of a mathematical algorithm is usually completely lost during an implementation. A mathematical rigorous and realistic model for computation on continuous structures is provided by computable analysis. The finite strings as codes for elements of a structure are replaced by total string functions that provide on demand information about the element they encode. Functions between encoded spaces can then be computed by operating on Baire space: The space of all total string functions. Computation on Baire space is done using oracle Turing machines. Intuitively, oracle Turing machines correspond to programs with function calls. It is not a priory clear which of these programs should be considered fast. We introduce the accepted class of polynomial-time computable operators on Baire space, i.e. we specify what programs with function calls should be considered efficient. The definition resembles classical polynomial-time computability very closely (due to work by Kapron and Cook). However, there are some important differences that we investigate in some detail.</span><br clear="all"><div><br></div>-- <br><div class="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div dir="ltr"><div dir="ltr">Luca Rossi</div><div dir="ltr"><br></div><div dir="ltr">Lecturer in Computer Science</div><div dir="ltr">School of Engineering and Applied Science</div><div dir="ltr">Aston University</div><div dir="ltr">Web: <a href="http://www.cs.bham.ac.uk/~rossil/" target="_blank">http://www.cs.aston.ac.uk/~rossil/</a></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div>
</div></div>