\documentstyle[12pt,fullpage]{article}
\begin{document}

\begin{center}
\LARGE\bf
${\bf 2^{nd}}$ Moscow -- Vienna Workshop \\
on Logic and Computation

\bigskip
\large
\it   Steklov Mathematical Institute \\
Moscow, 26--27 April, 2002
\end{center}

\large

%\bigskip

%\begin{center} {\Large\bf PROGRAM}
%\end{center}

\bigskip \bigskip
\noindent {\Large{\bf Friday, 26.04}} (Conference hall, 9-th floor) \\[3ex]
{\bf Morning session.} {\it Chair:} S.I. Adian.

\begin{description}
\item[10:30--11:00] Sergei N. Artemov:
Normalization and confluence in reflective lambda-calculus.

\item[11:00--11:30] Matthias Baaz:
Fast Cut-Elimination.

\item[11:30--12:00] Coffee-break. (Room 530, 5-th floor)

\noindent \phantom{Morning sessio} {\it Chair:} C. Ferm\"uller.


\item[12:00--12:30] Agata Ciabattoni:
Hypersequent calculi for G\"odel logics.

\item[12:30--13:00] Rostislav E. Yavorsky:
A generalization of the Solovay theorem on provability logic.

\item[13:00--15:00] Lunch.

\end{description}
%\newpage

\bigskip  \bigskip
\noindent {\bf Afternoon session.} {\it Chair:} L.D. Beklemishev.

\begin{description}
\item[15:00--15:30 ] Arnold Beckmann:
Bounded Arithmetic and Dynamic Ordinals.

\item[15:30--16:00] Vladimir N. Krupski:
A propositional proof theoretic interface for arithmetic.

\item[16:00--16:30] Coffee-break.  (Room 530, 5-th floor)

\item[16:30--17:00] A.V. Kudinov, V.B. Shehtman:
Some modal logics of topological spaces.

\item[17:00--17:30] Norbert Preining:
Classification of first order G\"odel logics.
\end{description}

\newpage
\bigskip
\noindent {\Large\bf Saturday, 27.04} (Conference hall, 9-th floor) \\[3ex]
{\bf Morning session.} {\it Chair:} S. Artemov.

\begin{description}
\item[10:30--11:00] Chris Ferm\"uller:
A Natural Deduction System for Intuitionistic Fuzzy Logic.

\item[11:00--11:30] A.G. Kravtsov:
 On extensions of the modal logic ${\bf SL}^n$.

\item[11:30--11:50] Coffee-break.  (Room 530, 5-th floor)

\item[11:50--12:20]  A.~V.~Chernov, D.~P.~Skvortsov,
E.~Z.~Skvortsova, N.~K.~Ve\-re\-shchagin:
Variants of realizability for propositional formulas and
the logic of the weak law of excluded middle.

\item[12:20--12:50] Georg Moser:
On generalizations of Simple Type.

\item[12:50--13:10] Coffee-break.  (Room 530, 5-th floor)
\end{description}

\bigskip
\noindent {\bf Afternoon session.} {\it Chair:} M. Baaz.
\begin{description}
\item[13:10--13:40] Lev D. Beklemishev:
On limit existence axioms in arithmetic.

\item[13:40--14:10] An. A. Muchnik, A. L. Semenov:
Correlations between randomness of finite sequences and stability of the
frequences in simple subsequences.

\item[14:10--14:40] Helmut Veith:
Counterexamples in Model Checking.

\item[15:00\phantom{--24:00}] {\bf Lunch. Closing.} (Room 530, 5-th floor)

\end{description}
\end{document}



Ан. А. Мучник, А. Л. Семенов.

Соотношение между случайностью конечной последовательности и
стабильностью частот в простых выборках.


 An. A. Muchnik,  A. L. Semenov.

  Correlations between randomness of finite sequences and stability of the
frequences in simple subsequences.


 We consider the frequency approach to the randomness of finite sequences
proposed by Kolmogorov in 1963. Suppose we have a set of rules, which choose
a subsequence from any sequence of given length $N$. A sequence is called
$(n,\epsilon,p)$-\emph{random} with respect to this set if in any chosen
subsequence of length greater than $n$ the difference between the frequency
of ones and $p$ is less than $\epsilon$. Kolmogorov showed that if a set
of rules has size less than
$\frac{1}{2}\mathrm e^{2n\epsilon^2(1-\epsilon)}$, then there exist
$(n,\epsilon,p)$-random sequence. We prove that this bound is sharp,
i.~e., there exists a set of rules of almost the same size
such that any sequence is non-random with respect to this set.

And another natural question is considered. Let we have some small set
of sequences. Does a small set of rules exists such that
all our sequences are non-random with respect to it? The answer is positive.

