Walter Carnielli, UNICAMP (Org)
Anderson de Araújo (Center for Logic, Epistemology and History of Science (CLE) State University of Campinas (UNICAMP)
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)
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)
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)
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 re ete 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, exempli cando seu uso no método diagonal de Cantor e na de niçã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 signi cado 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)
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)
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.
References
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.
Download Brazilian Logic Conference Program 
Registrations are open for the XVI Brazilian Logic Conference/Logic School.
- RegistrationImportant Dates EBL begins at 13h, on May 9th (Monday) and ends at 18h, on May 13th (Friday)
LOGIC SCHOOL begins at 9h, on May 7th (Saturday) and ends at 20h on May 8th (Sunday) See important dates:
The Brazilian Embassies and Consulates abroad maintain updated web sites, that provide information about visas and entry requirements, such as immunizations, depending on where you are coming from, as well as other practical information and health tips. Please take some time to review the entry requirements to avoid unpleasant surprises.
Home | Description | Comittees | Program | Keynote Speakers | Turing Session | Call for papers | Submissions | Logic School | Registration | Proceedings | Touristic information
Siga o XVI EBL:
