Kitobdan sitatalar «Большой роман о математике. История мира через призму математики»

На этапах А и В были введены первые два члена последовательности: 1 и 1. На этапе C вычисляется сумма двух предыдущих чисел. На этапах D и Е в память заносятся последующие числа из ряда таким образом, чтобы алгоритм мог работать циклично. Если вы заходите проверить, как работает данный алгоритм, то сможете убедиться, что получится следующая последовательность чисел: 1, 1, 2, 3, 5, 8, 13, 21 и т. д. Несмотря на то, что алгоритм выглядит достаточно просто на первый взгляд, машина Тьюринга все еще не способна его обработать. В соответствии с определением, данным их автором, эта машина не может осуществлять операцию сложения, как это указано на этапе C. В ее функции входят только внесение, прочтение и замена элементов в памяти в соответствии с инструкциями на каждом этапе. Таким образом, можно задать ей алгоритм сложения, согласно которому числа складываются в соответствии с их разрядами и запоминанием чисел в уме, по аналогии со счетами. Другими словами, сложение не является частью аксиоматики машины, а это уже одна из ее теорем, которые должны иметь свой алгоритм для использования. После того как этот алгоритм будет составлен, он может быть использован на этапе C, и машина Тьюринга, таким образом, вычислит числа Фибоначчи. Повышая сложность задач, можно научить машину Тьюринга выполнять операции умножения, деления, возведения в квадрат, извлечения квадратного корня, находить решения уравнений и тригонометрические соотношения, вычислять приближенное значение числа π, определять декартовы координаты геометрических фигур или исчислять бесконечно малые величины. Таким образом, при условии составления соответствующих алгоритмов машина Тьюринга способна решать любые математические задачи, которые мы уже успели рассмотреть, причем точность таких расчетов будет значительно выше. Теорема о четырех красках Возьмем карту территории, состоящую из нескольких областей, отделенных друг от друга границами. Какое минимальное количество цветов необходимо использовать при их раскрашивании, чтобы две соседних области всегда были разного цвета?