Return to Answer

Applications of Kolmogorov complexity to computable model theory (2007).

In this paper we answer the following well-known open question in computable model theory. Does there exist a computable not ℵ$_0$-categorical saturated structure with a unique computable isomorphism type? Our answer is affirmative and uses a construction based on Kolmogorov complexity.

Logical operations and Kolmogorov complexity (2002).

Conditional Kolmogorov complexity can be understood as the complexity of the problem $Y\rightarrow X$, where $Y$ is the problem “construct $y$” and $X$ is the problem “construct $x$”. Other logical operations ($\wedge,\lor,\leftrightarrow$) can be interpreted in a similar way, extending Kolmogorov interpretation of intuitionistic logic and Kleene realizability.

Kolmogorov complexity and the second incompleteness theorem (1995.

It is well known that Kolmogorov complexity has a close relation with Gödel’s first incompleteness theorem. In this paper, we give a new formulation of the first incompleteness theorem in terms of Kolmogorov complexity, that is a generalization of Kolmogorov’s theorem, and derive a semantic proof of the second incompleteness theroem from it.

Four pointers to the literature from the last 25 years on applications of Kolmogorov complexity to mathematical logic:

Applications of Kolmogorov complexity to computable model theory (2007).

In this paper we answer the following well-known open question in computable model theory. Does there exist a computable not ℵ$_0$-categorical saturated structure with a unique computable isomorphism type? Our answer is affirmative and uses a construction based on Kolmogorov complexity.

Logical operations and Kolmogorov complexity (2002).

Conditional Kolmogorov complexity can be understood as the complexity of the problem $Y\rightarrow X$, where $Y$ is the problem “construct $y$” and $X$ is the problem “construct $x$”. Other logical operations ($\wedge,\lor,\leftrightarrow$) can be interpreted in a similar way, extending Kolmogorov interpretation of intuitionistic logic and Kleene realizability.

The Kolmogorov expression complexity of logics (1997).

We introduce the Kolmogorov variant of Vardi's expression complexity. We define it by considering the value of the Kolmogorov complexity $C(L[{\cal A}])$ of the infinite string $L[{\cal A}]$ of all truth values of sentences of $L$ in ${\cal A}$. The higher is this value, the more expressive is the logic $L$ in ${\cal A}$.

Kolmogorov complexity and the second incompleteness theorem (1995).

It is well known that Kolmogorov complexity has a close relation with Gödel’s first incompleteness theorem. In this paper, we give a new formulation of the first incompleteness theorem in terms of Kolmogorov complexity, that is a generalization of Kolmogorov’s theorem, and derive a semantic proof of the second incompleteness theorem from it.

Applications of Kolmogorov complexity to computable model theory (2007).

In this paper we answer the following well-known open question in computable model theory. Does there exist a computable not ℵ$_0$-categorical saturated structure with a unique computable isomorphism type? Our answer is affirmative and uses a construction based on Kolmogorov complexity.

Logical operations and Kolmogorov complexity (2002).

Conditional Kolmogorov complexity can be understood as the complexity of the problem $Y\rightarrow X$, where $Y$ is the problem “construct $y$” and $X$ is the problem “construct $x$”. Other logical operations ($\wedge,\lor,\leftrightarrow$) can be interpreted in a similar way, extending Kolmogorov interpretation of intuitionistic logic and Kleene realizability.

Applications of Kolmogorov complexity to computable model theory (2007).

In this paper we answer the following well-known open question in computable model theory. Does there exist a computable not ℵ$_0$-categorical saturated structure with a unique computable isomorphism type? Our answer is affirmative and uses a construction based on Kolmogorov complexity.

Logical operations and Kolmogorov complexity (2002).

Conditional Kolmogorov complexity can be understood as the complexity of the problem $Y\rightarrow X$, where $Y$ is the problem “construct $y$” and $X$ is the problem “construct $x$”. Other logical operations ($\wedge,\lor,\leftrightarrow$) can be interpreted in a similar way, extending Kolmogorov interpretation of intuitionistic logic and Kleene realizability.

Kolmogorov complexity and the second incompleteness theorem (1995.

It is well known that Kolmogorov complexity has a close relation with Gödel’s first incompleteness theorem. In this paper, we give a new formulation of the first incompleteness theorem in terms of Kolmogorov complexity, that is a generalization of Kolmogorov’s theorem, and derive a semantic proof of the second incompleteness theroem from it.

Applications of Kolmogorov complexity to computable model theory, The Journal of Symbolic Logic 72, 1041-1054 (2007).

In this paper we answer the following well-known open question in computable model theory. Does there exist a computable not ℵ$_0$-categorical saturated structure with a unique computable isomorphism type? Our answer is affirmative and uses a construction based on Kolmogorov complexity.

Applications of Kolmogorov complexity to computable model theory (2007).

In this paper we answer the following well-known open question in computable model theory. Does there exist a computable not ℵ$_0$-categorical saturated structure with a unique computable isomorphism type? Our answer is affirmative and uses a construction based on Kolmogorov complexity.

Logical operations and Kolmogorov complexity (2002).

Conditional Kolmogorov complexity can be understood as the complexity of the problem $Y\rightarrow X$, where $Y$ is the problem “construct $y$” and $X$ is the problem “construct $x$”. Other logical operations ($\wedge,\lor,\leftrightarrow$) can be interpreted in a similar way, extending Kolmogorov interpretation of intuitionistic logic and Kleene realizability.