Bonjour à tous,
Nous avons le plaisir d'accueillir Daniel Leivant à la prochaine séance du séminaire PPS du:
Turing in the sky: machine models for the arithmetical and analytical hierarchies
Daniel Leivant (Indiana University & LORIA Nancy)Résumé: Alternating Turing machines (ATMs) were invented by Chandra and Stockmeyer (1976) as a generalization of nondeterministic machines. Just like nondeterminstic machines, their interest is not in physical implementation, but as a theoretical tool, since they elegantly bridge time and space. For example, alternating Log-space is PTime, and alternating PTime is Pspace. However, ATMs have not been studied much beyond complexity theory, since any language accepted an ATM is accepted already by a deterministic TM. The underlying reason is that the semantics of ATMs is defined "locally".
We consider a more global semantics for ATMs, which agrees with the tranditional local semantics for time-bounded computations. Surprisingly, our broader semantics has far-reaching consequences: our revised machines accept precisely the inductive (i.e. Pi-1-1) languages, that is the second-order analog of the RE languages.
Alternating deciders, which either accept or reject each input, accept precisely the hyper-elementary (= Delta-1-1) languages. Alternating machines with a uniform bound k on alternations accept precisely level k of the arithmetical hierarchy. Using negation states, with a suitable semantics, ATMs exhaust the entire analytical hierarchy; in fact, the languages accepted by alternating TMs with at most k negation states along any computation trace are precisely the Pi_k^1 languages.
À NOTER: il y aura café, thé, etc... un quart d'heure avant le début du séminaire: venez un peu en avance!
Plus de détails sur le séminaire à http://www.pps.jussieu.fr/seminaire.
Amicalement,
Alexis
Aucun commentaire:
Enregistrer un commentaire