On Series of Ordinals and Combinatorics

This paper deals mainly with generalizations of results in finitary combinatorics to infinite ordinals. It is well-known that for finite ordinals ∑_bT<αβ is the number of 2-element subsets of an α-element set. It is shown here that for any well-ordered set of arbitrary infinite order type α, ∑_bT<αβ is the ordinal of the set M of 2-element subsets, where M is ordered in some natural way. The result is then extended to evaluating the ordinal of the set of all n-element subsets for each natural number n ≥ 2. Moreover, series ∑_β<αf(β) are investigated and evaluated, where α is a limit ordinal and the function f belongs to a certain class of functions containing polynomials with natural number coefficients. The tools developed for this result can be extended to cover all infinite α, but the case of finite α appears to be quite problematic.     

Computational Complexity in Algebraic Systems

Computability and computational complexity were first considered over the fields of real and complex numbers and generalized to arbitrary algebraic systems. This article approaches the theory of computational complexity over an arbitrary algebraic system by taking computability over the list extension for a computational model of it. We study the resultant polynomial complexity classes and mention some NP-complete problems.     

On Computability of Decaying and Nondecaying States in Quantum Systems with Cantor Spectra

We study Hamiltonians with singular spectra of Cantor type with a constant ratio of dissection. The decay properties of the states in such systems depend on the nature of the dissection rate that can be characterized in terms of the algebraic number theory. We show that in spite of simplicity of the considered model the computational modeling of nondecaying states is in general impossible.     

Importance of the choice of assumptions and models in the estimation of analytical quality specifications

The validity of any model depends on its ability to imagine the situation or problem to which it is applied. Further, the assumptions made in relation to the model are determining for the actual outcome. Within the field of clinical biochemistry a lot of models for analytical quality specifications, based on a variety of concepts and ’clinical settings’, have been proposed. A hierarchical structure for application of these approaches and models has been agreed on at several occasions in 1999. In this hierarchy, the highest rank is given to evaluation of analytical quality specifications based on ’clinical settings’/’clinical outcome’ models, followed by specifications based on biological variation and on ’clinicians opinions’. This contribution, deals with the problems of combining random and systematic errors and the implications of application of different models to a variety of clinical settings. Received: 1 June, 2002 Accepted: 17 July 2002 Presented at the European Conference on Quality in the Spotlight in Medical Laboratories, 7–9 October 2001, Antwerp, Belgium     

Classical physics and Penrose's thesis

We expose and discussPenrose's thesis: Nature produces harnessable noncomputable processes, but none at the classical level. We then suggest a partial counterexample to it, based on aGedanken experiment about an undecidable family of integrable Hamiltonian systems that could lead to a sort of idealized solution to the Halting problem for Turing machines.1. Partially supported by a Fulbright/CNP_q-Brazil grant. Permanent address after November 5, 1990: Center for the Study of Mathematical Theories of Communication, IDEA/School of Communications, Federal University of Rio de Janeiro, Av. Pasteur 250, 22290 Rio de Janeiro, RJ Brazil.     

Quantum Principles and Mathematical Computability

Taking the view that computation is after all physical, we argue that physics, particularly quantum physics, could help extend the notion of computability. Here, we list the important and unique features of quantum mechanics and then outline a quantum mechanical “algorithm” for one of the insoluble problems of mathematics, the Hilbert's tenth and equivalently the Turing halting problem. The key element of this algorithm is the computability and measurability of both the values of physical observables and of the quantum-mechanical probability distributions for these values.     

On the Relation of Σ-Reducibility Between Admissible Sets

Reducibility on admissible sets is studied which is a stronger version of the usual -presentability of models. One of its informal prototypes is the interpretability of one computational device in the other. We obtain criteria of reducibility for recursively listed and pure sets, introduce the notion of jump, and prove exact boundaries for the ordinals of jumps. We also show that this reducibility is lifted to -superstructures. Several results are proven on the relations of this reducibility to some known reducibilities.     

Graphical Models for Ordinal Data

This article considers a graphical model for ordinal variables, where it is assumed that the data are generated by discretizing the marginal distributions of a latent multivariate Gaussian distribution. The relationships between these ordinal variables are then described by the underlying Gaussian graphical model and can be inferred by estimating the corresponding concentration matrix. Direct estimation of the model is computationally expensive, but an approximate EM-like algorithm is developed to provide an accurate estimate of the parameters at a fraction of the computational cost. Numerical evidence based on simulation studies shows the strong performance of the algorithm, which is also illustrated on datasets on movie ratings and an educational survey.     

Continuous Utility Representation Theorems in Arbitrary Concrete Categories

In this paper the continuous utility representation problem will be discussed in arbitrary concrete categories. In particular, generalizations of the utility representation theorems of Eilenberg, Debreu and Estévez and Hervés will be presented that also hold if the codomain of a utility function is an arbitrary totally ordered set and not just the real line. In addition, we shall prove and apply a general result on the characterization of structures that have the property that every continuous total preorder has a continuous utility representation. Finally, generalizations of the utility representation theorems of Debreu and Eilenberg will be discussed that are valid if we consider arbitrary binary relations and allow a utility function to have values in an arbitrary totally ordered set.