Инструментовка. Эта задача представляет собой еще один случай, когда почти любой язык имеет как достоинства, так и недостатки; следует, однако, избегать интерпретативных языков ввиду малого размера внутреннего цикла.
Длительность исполнения. Одному исполнителю на 1 неделю.
Литература
Дэвис (Davis M.). Computability and Unsolvability, McGraw-Hill, New York, NY, 1958.
Дэвис приводит с изматывающими подробностями все те доказательства, которые другие авторы «оставляют читателю». Прочитав Дэвиса от корки до корки, вы уже никогда не усомнитесь в справедливости любого утверждения о мощи машины Тьюринга. Впрочем, вполне возможно, что у вас навсегда пропадет охота что бы то ни было слышать об этой машине.
Хопкрофт, Ульман (Hopcroft J. E., Ullman J. D). Formal Languages and Their Relation to Automata. Addison-Wesley, Reading, MA, 1969.
Книга Хопкрофта и Ульмана — наилучший в своей области учебник для аспирантов первого года обучения. В ней содержатся все основные результаты о машинах Тьюринга, причем они излагаются в контексте других классов автоматов Книга полезна также своей обширной библиографией.
Минский (Minsky M. L.). Computation: Finite and Infinite Machines. Prentice-Hall, Englewood Cliffs NJ, 1967.
Минский дает прекрасное, легко воспринимаемое введение в теорию автоматов. Это, вероятно, наиболее подходящая книга для первого знакомства с предметом.
*Трахтенброт Б. А. Алгоритмы и вычислительные автоматы. — М.: Советское радио, 1974.
14.
Машинные забавы,
или Стратегия компьютера при игре в калах
Дискуссии о «разумном» поведении компьютеров начались задолго до появления реальных вычислительных машин. Многие согласятся, что высокое мастерство в какой-либо интеллектуальной игре, не поддающейся полному анализу, должно свидетельствовать о незаурядных умственных способностях игрока. Если компьютер к тому же обучаем, то отрицать его интеллект еще труднее. Говоря о машинной игре, чаще всего имеют в виду шахматы, однако даже самые лучшие программы оказываются на уровне весьма посредственных шахматистов. Но в других играх можно достичь большего успеха.
Калах, известный также и под другими названиями (манкала, вари, овари), — это старинная африканская игра. По ее теории написано очень мало, тем не менее в течение столетий в калах играют с помощью камешков представители самых разных культур. Хотя игра эта — чистая борьба умов, не содержащая какого-либо случайного элемента, африканцы режутся в нее постоянно. Благодаря нехитрому инвентарю и простым правилам, калах великолепно подходит и для игры с машиной. Как показывают современные исследования, компьютер с программой наподобие предлагаемой здесь играет в калах лучше любого человека.
