Может ли обезьяна воссоздать произведение Шекспира, случайно ударив по клавиатуре?
Я имею в виду написание программы, которая будет случайным образом генерировать строку из N символов, где N - это количество символов в книге X, включая пробелы, правильную пунктуацию и использование заглавных букв. Во время каждой генерации случайных символов я буду проверять, соответствует ли вывод фактическому тексту книги X.
Предполагая, что используется английский алфавит с некоторыми нормальными грамматическими правилами, закодированными в генераторе, возможно ли в вычислительном отношении написать программу для случайного генерирования текста книги X?
Какие виды оптимизации могут быть реализованы для облегчения решения проблемы?
Какое время работы вам понадобится при использовании современного четырехъядерного (i5) настольного компьютера. Как насчет использования суперкомпьютера?
Грубо говоря, каждая страница книги в твердом переплете стандартного формата содержит около 300-350 слов, и каждое слово состоит из пяти символов плюс пробел. Так, типичная страница книги имеет, скажем, от 1500 до 1800 символов (не считая пробелов). Если мы рассмотрим 250 страниц в качестве стандартной длины книги, то вы говорите о 400 000 символов, если не считать пробелы; 500 000, если вы делаете. источник
Итак, если предположить, что книга X имеет 500 000 символов и наш алфавит имеет размер 30. Можно ли сделать что-то лучше, чем 30^500 000 ~(4,2 × 10^738560)?
3 ответа
Если вы ищете идею, настолько сумасшедшую, что никто другой не попробовал ее, вам придется попробовать больше:-) - см. http://www.bbc.co.uk/news/technology-15060310,,
Несколько миллионов виртуальных обезьян близки к воссозданию полного собрания произведений Шекспира путем случайного нажатия клавиш на виртуальных пишущих машинках.
Подведение итогов того, насколько хорошо они работают, показывает, что воссоздание завершено на 99,990%.
Первой единственной работой, которая будет закончена, была поэма "Жалоба любовника".
Созданный американским программистом Джесси Андерсоном, проект координирует работу виртуальных обезьян, работающих в облачной вычислительной системе Amazon EC2 через домашний ПК.
(+ много дополнительной информации, включая практический опыт работы с настоящими обезьянами)
Вместо перестановки символов вы можете смоделировать это как перестановку слов - большинство книг используют мало, если какие-то новые слова (за исключением таких книг, как "Сквозное зеркало" Льюиса Кэрролла) - вам, вероятно, нужно смоделировать стихотворение "Jabberwocky" "как перестановка символов). Кроме того, большинство слов в словаре не используются в литературе, так что вы, вероятно, можете ограничиться словарем, скажем, из 10000 наиболее часто используемых слов и по-прежнему составлять большинство книг.
Использование грамматики для ограничения порядка слов сложнее, потому что многие книги используют недопустимые порядки слов (особенно в диалоге). Возможно, вы могли бы использовать стандартный анализатор английского языка для предложений, которые не в кавычках (то есть не в диалоге), чтобы отфильтровать недопустимые порядки слов, а затем использовать прямую перестановку слов для предложений, которые находятся в кавычках. Очевидно, что это не сработает для такой книги, как "Улисс", где законы грамматики выбрасываются в окно.