Машина Поста, самореференция и парадоксы

Abstract

Иерархический подход Рассела-Тарского рассматривает явление самореференции в качестве унифицированной причины возникновения обширного семейства различных семантических парадоксов. Появление в конце XX в. инфинитных форм парадоксов без признаков самореференции сделало иерархический подход Рассела-Тарского объектом многочисленных критических атак. На примере парадокса «Бесконечного лжеца» С. Ябло исследуются аналитические возможности оригинальной вычислительной семантики, исключающей любые виды рекурсии при определении истинностного значения и Демонстрирующей эффективность базовых принципов иерархического подхода Рассела-Тарского в борьбе против новых форм семантических парадоксов.

The Russell-Tarski hierarchical approach regards self-reference as a unified source of the emergence for a broad family of various semantic paradoxes. The Russell-Tarski hierarchical approach became the object of numerous critical attacks after the appearance of infinite forms of paradoxes without self-reference at the end of the 20th century. The “Infinite Liar” proposed by the American logician Stephen Yablo, in particular, is usually seen as the most powerful and convincing counterargument against the Russell-Tarski hierarchical approach. The “Infinite Liar” does not contain selfreference. Each of the sentences of this infinite sequence does not speak of itself, but always only of all the following sentences, and the logical construction of this paradox is obviously isomorphic to the hierarchical structure as such. However, the truth-values of individual sentences in the “Infinite Liar” are based on recursive functions. The “Infinite Liar” by Yablo provides analytical possibilities for constructing the original computational semantics that excludes any kind of recursion in determining the truth-value, and it demonstrates effectiveness of the basic principles of the Russell-Tarski hierarchical approach in the struggle against new forms of semantic paradoxes. The “Infinite Liar” sentences are transformed into a modified computational algorithm for the Post machine. The analysis shows that for any initial state of the tape and the starting position of the cell marking mechanism, the “Infinite Liar” algorithm is quite feasible for the Post machine. The absence of a Post machine nonresultative stop in performing the “Infinite Liar” is explained by the fact that the computational algorithm of such a program has the form of a monotonous hierarchical structure in which every arbitrary sentence Sn of an infinite sequence fixes the meaning of strictly following sentences Sn+1, Sn+2,..., Sn+m, which completely excludes any form of recursive definitions. The disappearance of monotony in the hierarchical structure of the so-called “Dietary Infinite Liar” almost instantly leads to a nonresultative stop of the Post machine at any initial state of the tape and the starting position of the cell marking mechanism. The difference in performing demonstrated by the Post machine when executing the programs of the “Infinite Liar” and the “Dietary Infinite Liar” is a clear evidence of the effectiveness of the basic principles of the Russell-Tarski hierarchical approach in the struggle against new forms of semantic paradoxes. That is why the ban of sentences (or their sequences) with self-reference remains the most popular of standard ways in the struggle against semantic paradoxes.