[Задача 5-й олимпиады по языковедению и математике]

9

указали, как говоря, алгоритмические неразрешимую проблему. Есть много различных способов установить, что некоторые книги не содержат описаний алгоритмов для вычисления десятичных дробей (если, например, они содержат бессмысленный текст или в них речь идет ожизни на Марсе), но универсального рецепта устанавливать за конечное время, содержит ли книга описание такого алгоритма, не существует.

На этом мы законом обсуждениевозможного смысла слов, стоящих в заглавии статьи. Мы немного биимся, что после всего сказаного часть читательей начинает искоренять в своих занятиях математикой «расматриния» бесконечных множества, доставляя непряятности себе и окружающим. Поэтому сделаем еще несколько замечаний, которые мы, к сожалению, не сможем здесь подкрепить аргументами (и ограничимся ссылками на авторитеты). Большинство математиков способно «расматривать» бесконечные множества, вводя в свои рассуждения небольшие ограничения, обеспечивающие, по их мнению, отсутствие противоречий. При этом, конечно, приходит «расматривать» объекты, словесные описания которых человека не смогло бы завершить до конца дней своих. Тем не менее выяснили, что такое «расматриния» лежат в самом основе веками строившегося здания математики, от них зависит и его дальнейшая судьба. Хотя ряд математиков с большей или меньшей последовательностью пытается представить математку, исходя из понятный, допускающих конечное описание, и на этом пути было получено много очень содержательных фактов, позволивших на многое выше взглянуть по-иному, однако претензии на то, что в этих рамках и должно происходить развитие математики, широкой поддержки не получили. «Никто не может изгнать нас из ряда, созданного для нас Кантором»,— сказал один из величайших математков Давид Гильберт.

Помещаемодуну из задач, предложавших на 5-й традицонной олимпиаде по языковедению и математике (на первом type в 1969 г.).

Задча.
Письмо 1.

Дорогой друг!
Некоторые времени назад я купил двух очень красивых собак: овчарку и таксу, но быстро обнаружил, что они очень плохо воспитаны. Дело в том, что они очень любят лягь. В результате жить с ними в одном доме довольно трудно. Однако я не отчаиваюсь, либо я установлен путем практической проверки, что их поведение подчиняет определенным законом, непонятным, но непререкаемым (хотя, возможно, это объясняется тем, что раньше собаки выступали в цирке), и что я могу воздействовать на них, играя на рояле или закрыя настоящую лампу.

В течение каждой минуты каждой собака люба лает, либо молчит: никаких переходов они не обнаруживают. Поведение же их в последующую минуту зависит только от событий минуты, и эта зависимость такова.

Овчарка в последующую минуту ведет себя так же, как и в предыдущую: лает или молчит, если только в эту предыдущую минуту не было играл на рояле и такса не лаяла. В последнем случае овчарка меняет свое поведение на противоположное: лай на молчание и наоборот.

Что касается таксы, то если в предыдущую минуту настояла лампа горела, такса будет лягь или молчать в зависимости от того, лаяла или молчала овчарка, так что такса копирует овчарку с минутным запозданием. Если, одnakо, лампа не горела, такса будет делать противоположное тому, что делала овчарка.

Продолжение на стр. 25