### arnold beckmann's pages

## Generalised dynamic ordinals - universal measures
for implicit computational complexity

**File:** PDF-File

**Author:** Arnold Beckmann

**Title:** Generalised dynamic ordinals - universal measures
for implicit computational complexity

**Journal:** *Logic Colloquium '02*,
Lecture Notes in Logic **27**: 48-74,
Association for Symbolic Logic, La Jolla, CA, 2006.

**DOI:** 10.1017/9781316755723.004

**Abstract:**
We extend the definition of dynamic ordinals to
generalised dynamic ordinals.
We compute generalised dynamic ordinals of *all* fragments
of relativised bounded arithmetic by utilising methods from
Boolean complexity theory, similar to [Krajicek1994].
We indicate the role of generalised dynamic ordinals as universal measures
for implicit computational complexity.
I.e., we describe the connections between generalised dynamic ordinals and
witness oracle Turing machines for bounded arithmetic theories.
In particular, through the determination of generalised dynamic ordinals we
re-obtain well-known independence results for relativised bounded arithmetic
theories.