Machines from Turing to Quantum
Walter Carnielli, UNICAMP (Org)

Anderson de Araújo (Center for Logic, Epistemology and History of Science (CLE) State University of Campinas (UNICAMP)

A uniform halting protocol for quantum Turing machines

Although in these days quantum computing is one of the main lines of research in computer science, the foundations of quantum computability still are not well established. Notably, the halting of quantum computations is a problem for an adequate definition of Turing machines in accordance with the postulates of quantum mechanics. The aim of this paper is just to present a uniform definition of quantum Turing machines with a protocol for the halting of quantum computations which overcomes the known problems. The new definition of the halting of quantum Turing machines relies on the design of quantum computation as partial functions. The main result of the paper shows that the probability of the final configuration of a quantum Turing machine is not disturbed by any measurement or any coherence due to the time evolution after completing the computation, which are the desired properties of the halting for quantum computations.

Andrey Bovykin (Department of Mathematics - University of Bristol)

Turing-complete and arithmetically-complete templates: the atlas and the theory of all possible machines

Since the beginnings of modern unprovability theory in the 1980s, our picture of the space of all arithmetical possibilities has changed. Now, provable equivalence classes of consistencies, 1-consistencies, 2-consistencies, etc, of all classical theories can be expressed as short simple statements that match given patterns or 'templates'.
We are going to present two important templates that are closely entangled: the atlas of all polynomial equations with quantifier-prefixes and the theory of all possible machines. Both templates are arithmetically complete, so all classical unprovable statements, such as the Paris-Harrington Principle and Proposition E have expressions in terms of polynomials and in terms of halting of machines of certain kinds. We will go a bit deeper into the structure of these templates to understand seeds, arithmetical splitting, hidden classes and hopping between classes.
Machines of kind 0 are algorithms for a ruler. Machines of kind 1 are algorithms for ruler and compass. Machines of kind 2 are algorithms for Kempe linkages. Having fixed a 'language of tasks' that we set for our machines to do, it is an important problem to study the questions of decidability, undecidability and gauge statements about machines in terms of their provable equivalence classes. We will list some preliminary results and some open problems on this topic.

Gregory Chaitin (University of Buenos Aires, HCTE/UFRJ)

Turing as a Biologist

Few people remember Turing's work on pattern formation in biology (morphogenesis), but Turing's famous 1936 paper \emph{On Computable Numbers} exerted an immense influence on the birth of molecular biology indirectly, through the work of John von Neumann on self-reproducing automata, which influenced Sydney Brenner who in turn influenced Francis Crick, the Crick of Watson and Crick, the discoverers of the molecular structure of DNA. Furthermore, von Neumann's application of Turing's ideas to biology is beautifully supported by recent work on evo-devo (evolutionary developmental biology). The crucial idea: DNA is multi-billion year old software, but we could not recognize it as such before Turing's 1936 paper, which according to von Neumann creates the idea of computer hardware and software.

José Carlos Cifuentes (UFPR)

Cantor, Turing e o princípio finitista arquimediano: uma introdução à teoria dos aritmos

Neste trabalho, o princípio nitista arquimediano (PFA) é a seguinte propriedade dos números naturais:

Uma versão equivalente, aparentemente mais forte, é a seguinte:

Os termos 'número natural' e 'número nito', nas duas versões do PFA têm, como os números n e m, estatutos epistemológicos diferentes, sendo que por trás delas está implícita a seguinte versão informal que chamaremos de princípio nitista heurístico (PFH):

entre um número natural e outro só há um número nito de números naturais ,

que reete principalmente o fato de um processo que envolve números naturais poder ser feito num número nito de passos.
O PFH é tão claro para a matemática como o é a noção de 'calculabilidade efetiva', embora não o seja para a epistemologia, exemplicando seu uso no método diagonal de Cantor e na denição de máquina de Turing. A equivalência entre o PFA e o PFH pode ser considerada uma lei natural"assim como a tese de Church o é, pois baseia-se em considerações heurísticas.
O PFA é equivalente ao princípio de indução nita, fato que permitir-nos-á encontrar um sistema de axiomas equivalente ao de Peano que inclua o PFA em substituição do de indução. Esse sistema também motivará a teoria dos aritmos na qual o PFA adquire o signicado algébrico do teorema fundamental da aritmética. Nessa teoria é possível formular uma versão não-linear do princípio de indução nita.

Francisco Antonio Doria (PEP and COPPE/UFRJ)

On Hypercomputation

We notice that ideal analog computers can decide undecidable sentences in arithmetic, and discuss possible ways to build a hypercomputer, that is, a computer thet performs strictly stronger than Turing machines.

Manuel Doria (Junior researcher, APIT-PEP, COPPE/UFRJ)

Computing Devices as Real Patterns

After proposals ranging from natural computation in molecular biology (Shapiro 2007) to the pancomputationalism of digital physics (Wheeler 1990), a worry emerges that the ontology of natural sciences is becoming overpopulated with computers, to the threat of triviality for computationalist theses (Mi?kowski 2007). Following Daniel Dennett's theory of Real Patterns (Dennett 2001) and their posterior refinements (Ross 2000, Ladyman & Ross 2007), objective constraints are presented in information-theoretic terms on wether a given physical system is also a computational system. A novel response is also given to famous arguments hostile to computationalism by John Searle (Searle 1990) and Hillary Putnam (Putnam 1988) under which the computational perspective in secured as imperative in scientific theorizing.

Don Ross (2000). in Dennett's Philosophy: A Comprehensive Assessment. MIT Press.
Daniel C. Dennett (1991). Real Patterns. Journal of Philosophy 88 (1):27-51.
James Ladyman (2007). Every Thing Must Go: Metaphysics Naturalized. Oxford University Press.
Putnam, H. (1988). Representation and Reality. MIT Press.
Searle, J.R. (1990). Is the brain a digital computer? Proceedings and Addresses of the American Philosophical Association 64:21-37.

© 2011 - XVI EBL - Brazilian Logic Conference / Logic School / May 7th – 13th, 2011 Contact us
Home | Description | Comittees | Program | Keynote Speakers | Turing Session | Call for papers | Submissions | Logic School | Registration | Proceedings | Touristic information

Siga o XVI EBL:
 Logotipo do You Tube Logotipo do Facebook Logotipo do Linkedin Logotipo Blog Logotipo do Twitter

Valid CSS!        CSS válido!       Valid XHTML 1.0 Transitional