In this paper we deal with Fixpoint Arithmetic and Infinite Time Turing Machines. We show that every set of first order assignments definable by a formula of fixpoint arithmetic can be recognized by an Infinite Time Turing Machine, and that the resulting inclusion is proper. Our result, combined with other known results, gives a chain of proper inclusions from Pi(1)(1) to Fixpoint Arithmetic to Infinite Time Turing Machines to Delta(2)(1). (C) 2004 Elsevier B.V. All rights reserved.

On fixpoint arithmetic and infinite time Turing machines,

LENZI, Giacomo;
2004-01-01

Abstract

In this paper we deal with Fixpoint Arithmetic and Infinite Time Turing Machines. We show that every set of first order assignments definable by a formula of fixpoint arithmetic can be recognized by an Infinite Time Turing Machine, and that the resulting inclusion is proper. Our result, combined with other known results, gives a chain of proper inclusions from Pi(1)(1) to Fixpoint Arithmetic to Infinite Time Turing Machines to Delta(2)(1). (C) 2004 Elsevier B.V. All rights reserved.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11386/1954364
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 2
social impact