Незнайка составил программу для компьютера с ограниченной внешней памятью, которая печатает по 100 цифр каждую секунду. Незнайка утверждает, что если компьютеру позволить работать бесконечно долго, то он напечатает в точности десятичную запись числа "корень из 2" . Прав ли он?

задан 24 Сен '17 21:59

1

Каждая следующая конфигурация однозначно определена предыдущей. Если используемая память ограничена числом N бит, то в пределах 2^N+1 шагов будут происходить повторения. Тогда компьютер будет печатать то же самое. Это значит, что последовательность цифр окажется периодической с некоторого члена. Тем самым, она задаст рациональное число, и sqrt(2) таким способом не получить.

(24 Сен '17 22:22) falcao

"Каждая следующая конфигурация однозначно определена предыдущей." @falcao, Что понимать под конфигурацией и почему она определена однозначно?

(26 Сен '17 0:30) Аллочка Шакед

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

(26 Сен '17 0:42) falcao

Или, переводя с латыни на русский и слегка подправляя грамматику, что на текущее состояние действуют только предыдущие состояния… Забавные фокусы этимологии!

(26 Сен '17 15:25) abracadabra-...
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×91
×55

задан
24 Сен '17 21:59

показан
225 раз

обновлен
26 Сен '17 15:25

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru