# SOFSEM 2012 := Invited Speakers

## Foundations of Computer Science

SPECIAL EVENT: **SESSION ON TURING MACHINES**.

- Felipe Cucker (City University of Hong Kong, Hong Kong )
**The Legacy of Turing in Numerical Analysis**

*Alan Mathison Turing is revered among computer scientists for laying down the foundations of theoretical computer science via the introduction of the Turing machine, an abstract model of computation upon which, an elegant notion of cost and a theory of complexity can be developed. In this paper we argue that the contribution of Turing to "the other side of computer science", namely the domain of numerical computations as pioneered by Newton, Gauss, ..., and carried out today in the name of numerical analysis, is of an equally foundational nature.*

- Peter van Emde Boas (University of Amsterdam, The Netherlands )
**Turing Machines for Dummies**

*Regardless the precise formal model for Turing Machines used by some author, all authors agree on the fact that a full configuration arising during the computation of such a device must consist of three parts: 1) a finite section of tape with the symbols currently printed at each cell within this segment (all tape cells outside this segment implied to be blanks), 2) the current state of the finite control of the machine, and 3) the position of the reading head within the sequence of tape cells.*

For mathematicians it is irrelevant how these configurations are formally written down as a sequence of symbols. One simply can write a triple of objects, or (alternatively) one can write down the sequence of tape symbols, marking the presently scanned symbol by printing the state symbol above, below or in front of the tape symbol (called the concise notation herafter). Both styles of notations have been used throughout the literature (in fact the concise notation is mentioned already in Turing's original paper). Only much later during the earlier days of Complexity Theory it was realized that using the concise notation has advantages when Turing machines are playing their part in Complexity Theory: proving lower bounds or impossibility results.

Presumably we can identify Larry Stockmeyer to be the first author having clearly brought forward these advantages to our knowledge. In my talk I will present an overview of some applications where the concise notation has been found to be useful.

- Jiří Wiedermann (Institute of Computer Science, Academy of Sciences, Czech Republic )
**Towards Computational Models of Artificial Cognitive Systems that Can, in Principle, Pass the Turing Test**

*We will give plausible arguments in favor of a claim that we already have sufficient knowledge to understand the working of interesting artificial minds attaining a high-level cognition, consciousness included. Achieving a higher-level AI seems to be not a matter of a fundamental scientific breakthrough but rather a matter of exploiting our best theories of artificial minds and our most advanced data processing technologies. We list the theories we have in mind and illustrate their role and place on the example of a high-level architecture of a conscious cognitive agent with a potential to pass the Turing test.*

## Software & Web Engineering

## Cryptography, Security, and Verification

## Artificial Intelligence

SPECIAL EVENT: **SESSION ON TURING MACHINES**.