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.