Почему компьютер является универсальной машиной для работы с информацией
Обновлено: 03.07.2024
12 июня. Универсальная вычислительная машина
Предками программ были математические алгоритмы. Они работают одинаково: предоставляется некоторый ввод определенного формата, выполняется определенный набор операций и преобразований, а затем выдается вывод в соответствии с пожеланиями дизайнера. Вплоть до 1936 года все компьютеры любого типа предназначались для определенной цели, например, калькулятор. В качестве побочного продукта своих исследований в области формальной логики Алан Тьюринг разработал машину, которую можно было перепрограммировать для выполнения любого алгоритма. Логическая вычислительная машина задумывалась как теоретический аргумент, но она повлияла на разработку аппаратного обеспечения того времени и положила начало цифровой эпохе.
Универсальная вычислительная машина, также известная как машина Тьюринга, представляет собой абстрактную математическую модель, которая описывает, как может выполняться любая вычислительная логика.
Ключевой частью приведенного выше определения является слово «любой». Машина Тьюринга является основой архитектуры фон Неймана, которая, в свою очередь, является базовой структурой всех современных форм вычислений, включая критически важную способность хранить программы и данные и перепрограммировать компьютеры для выполнения множества функций. Все современные компьютеры — это машины Тьюринга, и даже более того, наше понимание вычислений основано на фундаменте машины Тьюринга. В свое время Тьюринг использовал свои машины для решения проблемы остановки и выдвинул тезис Черча-Тьюринга.
Требования:
Универсальная вычислительная машина должна иметь возможность принимать любые входные данные и преобразовывать их в желаемые выходные данные, используя любую программу или алгоритм, которые ей даны. Он должен уметь делать все то же, что и любая другая машина.
Механика:
Чтобы понять, как машины Тьюринга представляют все современные компьютеры, мы должны сначала понять компьютеры XIX века. Во времена Тьюринга компьютер был профессией человека, который садился с ручкой и бумагой и вычислял математические операции для целей страхования, финансов или инженерии. Человеку дали набор инструкций и черновую бумагу, на которой он мог преобразовать любой ввод в любой вывод точно в соответствии с инструкциями.
Очевидно, что они могли выполнять только одну операцию за раз. Чтобы быть детализированным, это включало в себя чтение инструкций, удерживание понимания в уме, чтение ввода, сравнение двух, затем запись вывода и переход к следующей задаче. Таким образом, человек-компьютер мог выполнять любую задачу, основанную на принятии решений, при условии, что ему были даны соответствующие инструкции.
У Тьюринга просто появилась новая идея попытаться воспроизвести этот человеко-компьютер как цифровой: универсальную вычислительную машину (или универсальную машину Тьюринга). Требовалась способность читать, писать и удерживать состояния/понимания, как у человека, а также держать как инструкции, так и рабочий документ. Тьюринг понял, что инструкции, черновой рабочий документ, входы и выходы можно свести воедино; это называется памятью.
Лента памяти неограниченной длины, разделенная на блоки. Заметьте, что необходимость бесконечности излишня и не парадоксальна; машине просто нужно достаточно места для работы программы.
Каждый из блоков содержит значения.
Эти значения записываются заранее заданным машинным алфавитом. Это «1» и «0» в современных компьютерах, которые используют изменения напряжения для интерпретации двоичного кода, но могут быть любыми в теоретической машине Тьюринга.
Голова чтения/записи, которая наводила курсор на один блок за раз, чтобы прочитать значение и
Переменная состояния, которая просто записывает определенный «статус» или «флаг», который используется в соответствии с регистром правил. Существует только конечное число определенных состояний, поэтому универсальная вычислительная машина известна как машина с конечным числом состояний.
Необходимо определить начальное состояние.
Необходимо определить состояние остановки.
Регистр правил (также называемый таблицей правил или таблицей конфигурации) — это список действий, которые головка чтения/записи должна выполнять в соответствии с состоянием и блокировкой, в которых она находится в данный момент, в любой момент времени. Представляет собой алгоритм или программу.
Они имеют общий вид: если блок = X и переменная состояния = Y, переместите один пробел на и измените переменную состояния на Z.
Например, в регистре правил будет указано: если блок = 1 и переменная состояния = 4, переместите головку чтения/записи на одну позицию влево и измените значение переменной состояния на 3.
Еще один способ описать вышеизложенное — диаграмма конечного автомата:
Каждый узел — это состояние, а каждое ребро — это правило в соответствии с регистром правил.Несколько параметров, разделенных от каждого узла, отражают различные значения блока, на котором находится головка чтения/записи.
Полнота по Тьюрингу. Как только программа может выполнять то, что может делать машина Тьюринга, она считается завершенной по Тьюрингу и считается высшей формой программы. В вычислительном отношении нет ничего выше этого.
Детерминистический. В некотором смысле кажется, что машина Тьюринга — это программа Event-Response. Некоторое состояние и некоторое значение блока создадут некоторый результат. На самом деле «программа» закодирована не в ленте, а в наборе правил, описывающих операции. Несмотря на это, именно эта основа означает, что компьютеры являются полностью детерминированными машинами и не могут создавать настоящую случайность.
Ограничения:
Машина Тьюринга во многих отношениях крайне неэффективна. Обратите внимание: хотя вы можете построить что-то быстрее, чем машина Тьюринга, вы не можете построить что-то, что вычисляет ее больше. Они выполняют только последовательные вычисления, что даже при технологическом совершенствовании асимптотически ограничивает физически возможный объем вычислений. В некоторой степени это можно обойти с помощью параллельных и квантовых вычислений.
Источники:
Шеннон, CE (1956). Универсальная машина Тьюринга с двумя внутренними состояниями. Исследования автоматов, 34, 157–165.
12 июня. Универсальная вычислительная машина
Предками программ были математические алгоритмы. Они работают одинаково: предоставляется некоторый ввод определенного формата, выполняется определенный набор операций и преобразований, а затем выдается вывод в соответствии с пожеланиями дизайнера. Вплоть до 1936 года все компьютеры любого типа предназначались для определенной цели, например, калькулятор. В качестве побочного продукта своих исследований в области формальной логики Алан Тьюринг разработал машину, которую можно было перепрограммировать для выполнения любого алгоритма. Логическая вычислительная машина задумывалась как теоретический аргумент, но она повлияла на разработку аппаратного обеспечения того времени и положила начало цифровой эпохе.
Универсальная вычислительная машина, также известная как машина Тьюринга, представляет собой абстрактную математическую модель, которая описывает, как может выполняться любая вычислительная логика.
Ключевой частью приведенного выше определения является слово «любой». Машина Тьюринга является основой архитектуры фон Неймана, которая, в свою очередь, является базовой структурой всех современных форм вычислений, включая критически важную способность хранить программы и данные и перепрограммировать компьютеры для выполнения множества функций. Все современные компьютеры — это машины Тьюринга, и даже более того, наше понимание вычислений основано на фундаменте машины Тьюринга. В свое время Тьюринг использовал свои машины для решения проблемы остановки и выдвинул тезис Черча-Тьюринга.
Требования:
Универсальная вычислительная машина должна иметь возможность принимать любые входные данные и преобразовывать их в желаемые выходные данные, используя любую программу или алгоритм, которые ей даны. Он должен уметь делать все то же, что и любая другая машина.
Механика:
Чтобы понять, как машины Тьюринга представляют все современные компьютеры, мы должны сначала понять компьютеры XIX века. Во времена Тьюринга компьютер был профессией человека, который садился с ручкой и бумагой и вычислял математические операции для целей страхования, финансов или инженерии. Человеку дали набор инструкций и черновую бумагу, на которой он мог преобразовать любой ввод в любой вывод точно в соответствии с инструкциями.
Очевидно, что они могли выполнять только одну операцию за раз. Чтобы быть детализированным, это включало в себя чтение инструкций, удерживание понимания в уме, чтение ввода, сравнение двух, затем запись вывода и переход к следующей задаче. Таким образом, человек-компьютер мог выполнять любую задачу, основанную на принятии решений, при условии, что ему были даны соответствующие инструкции.
У Тьюринга просто появилась новая идея попытаться воспроизвести этот человеко-компьютер как цифровой: универсальную вычислительную машину (или универсальную машину Тьюринга). Требовалась способность читать, писать и удерживать состояния/понимания, как у человека, а также держать как инструкции, так и рабочий документ. Тьюринг понял, что инструкции, черновой рабочий документ, входы и выходы можно свести воедино; это называется памятью.
Лента памяти неограниченной длины, разделенная на блоки. Заметьте, что необходимость бесконечности излишня и не парадоксальна; машине просто нужно достаточно места для работы программы.
Каждый из блоков содержит значения.
Эти значения записываются заранее заданным машинным алфавитом. Это «1» и «0» в современных компьютерах, которые используют изменения напряжения для интерпретации двоичного кода, но могут быть любыми в теоретической машине Тьюринга.
Голова чтения/записи, которая наводила курсор на один блок за раз, чтобы прочитать значение и
Переменная состояния, которая просто записывает определенный «статус» или «флаг», который используется в соответствии с регистром правил. Существует только конечное число определенных состояний, поэтому универсальная вычислительная машина известна как машина с конечным числом состояний.
Необходимо определить начальное состояние.
Необходимо определить состояние остановки.
Регистр правил (также называемый таблицей правил или таблицей конфигурации) — это список действий, которые головка чтения/записи должна выполнять в соответствии с состоянием и блокировкой, в которых она находится в данный момент, в любой момент времени. Представляет собой алгоритм или программу.
Они имеют общий вид: если блок = X и переменная состояния = Y, переместите один пробел на и измените переменную состояния на Z.
Например, в регистре правил будет указано: если блок = 1 и переменная состояния = 4, переместите головку чтения/записи на одну позицию влево и измените значение переменной состояния на 3.
Еще один способ описать вышеизложенное — диаграмма конечного автомата:
Каждый узел — это состояние, а каждое ребро — это правило в соответствии с регистром правил. Несколько параметров, разделенных от каждого узла, отражают различные значения блока, на котором находится головка чтения/записи.
Полнота по Тьюрингу. Как только программа может выполнять то, что может делать машина Тьюринга, она считается завершенной по Тьюрингу и считается высшей формой программы. В вычислительном отношении нет ничего выше этого.
Детерминистический. В некотором смысле кажется, что машина Тьюринга — это программа Event-Response. Некоторое состояние и некоторое значение блока создадут некоторый результат. На самом деле «программа» закодирована не в ленте, а в наборе правил, описывающих операции. Несмотря на это, именно эта основа означает, что компьютеры являются полностью детерминированными машинами и не могут создавать настоящую случайность.
Ограничения:
Машина Тьюринга во многих отношениях крайне неэффективна. Обратите внимание: хотя вы можете построить что-то быстрее, чем машина Тьюринга, вы не можете построить что-то, что вычисляет ее больше. Они выполняют только последовательные вычисления, что даже при технологическом совершенствовании асимптотически ограничивает физически возможный объем вычислений. В некоторой степени это можно обойти с помощью параллельных и квантовых вычислений.
Источники:
Шеннон, CE (1956). Универсальная машина Тьюринга с двумя внутренними состояниями. Исследования автоматов, 34, 157–165.
В 1936 году, во время учебы в докторантуре. в Принстонском университете английский математик Алан Тьюринг опубликовал статью «О вычислимых числах с приложением к проблеме Entscheidungsproblem», которая стала основой информатики. В нем Тьюринг представил теоретическую машину, способную решить любую задачу, которую можно описать простыми инструкциями, закодированными на бумажной ленте. Одна машина Тьюринга могла вычислять квадратные корни, а другая могла решать головоломки судоку. Тьюринг продемонстрировал, что можно сконструировать одну универсальную машину, которая могла бы имитировать любую машину Тьюринга. Одна машина, решающая любую проблему, выполняющая любую задачу, для которой может быть написана программа — звучит знакомо? Он изобрел компьютер.
В то время компьютеры были людьми; они составляли актуарные таблицы и производили инженерные расчеты. Когда союзники готовились ко Второй мировой войне, они столкнулись с острой нехваткой компьютеров для военных вычислений. Когда люди ушли на войну, дефицит увеличился, поэтому США механизировали проблему, построив Harvard Mark 1, электромеханического монстра длиной 50 футов. Он мог выполнять расчеты за считанные секунды, на которые у людей уходили часы.
Британцам также нужны были математики, чтобы взломать код Enigma немецкого флота. Тьюринг работал в сверхсекретной британской школе правительственного кода и шифров в Блетчли-парке. Там взлом кода стал промышленным процессом; 12 000 человек работали в три смены 24/7. Хотя поляки взломали «Энигму» еще до войны, нацисты усложнили машины «Энигмы»; было примерно 10 114 возможных перестановок. Тьюринг разработал электромеханическую машину под названием «Бомба», которая просматривала перестановки, и к концу войны британцы смогли считывать весь ежедневный трафик немецкой военно-морской «Энигмы». Сообщалось, что Эйзенхауэр сказал, что вклад Тьюринга и других в Блетчли сократил войну на целых два года и спас миллионы жизней.
По мере развития 1950-х бизнес быстро осознал преимущества компьютеров, и бизнес-вычисления превратились в новую отрасль.Все эти компьютеры были универсальными машинами Тьюринга — в том-то и дело, что их можно было запрограммировать на что угодно.
«Не будет никаких внутренних изменений [компьютера], даже если мы вдруг захотим переключиться с вычисления энергетических уровней атома неона на перечисление групп порядка 720. Может показаться несколько загадочным, что это можно сделать. Как можно ожидать, что машина будет делать все это многообразие вещей? Ответ заключается в том, что мы должны считать, что машина делает что-то очень простое, а именно выполняет приказы, отданные ей в стандартной форме, которую она способна понять». – Алан Тьюринг
К 1970-м годам родилось поколение, выросшее с «электронными мозгами», но им нужны были собственные персональные компьютеры. Проблема была в том, что они должны были их построить. В 1975 году некоторые любители создали Homebrew Computer Club; они были в восторге от потенциала новых кремниевых чипов, который позволил им создавать собственные компьютеры.
Один из участников Homebrew был бросившим колледж по имени Стив Возняк, который построил простой компьютер на основе микропроцессора 8080, который он подключил к клавиатуре и телевизору. Его друг Стив Джобс назвал его Apple I и нашел магазин в Силиконовой долине, который хотел купить 100 таких устройств по 500 долларов за штуку. У Apple была первая продажа, и зародилась культура стартапов Силиконовой долины. Другой бросивший колледж Билл Гейтс понял, что ПК нуждаются в программном обеспечении и что люди готовы платить за него — его Microsoft будет продавать программы.
Наследие Тьюринга не является полным. В 1950 году он опубликовал статью под названием «Вычислительные машины и интеллект». У него была идея, что компьютеры станут настолько мощными, что смогут думать. Он предвидел время, когда искусственный интеллект (ИИ) станет реальностью. Но как узнать, разумна ли машина? Он разработал Тест Тьюринга: судья, сидящий за компьютерным терминалом, задает вопросы двум объектам: человеку и компьютеру. Судья решает, какая сущность является человеком, а какая компьютером. Если судья ошибается, компьютер прошел тест Тьюринга и является разумным.
Хотя концепция ИИ Тьюринга еще не реализована, аспекты ИИ все чаще входят в нашу повседневную жизнь. Автомобильные спутниковые навигационные системы и поисковые алгоритмы Google используют искусственный интеллект. Siri от Apple на iPhone может понимать ваш голос и разумно реагировать. Производители автомобилей разрабатывают автомобили, которые сами управляются; Некоторые штаты США разрабатывают законопроект, разрешающий использование автономных транспортных средств на дорогах. Представление Тьюринга об искусственном интеллекте скоро станет реальностью.
В 1952 году Тьюринга привлекли к уголовной ответственности за грубую непристойность, поскольку в то время в Великобритании гомосексуализм считался преступлением. Его приговорили к химической кастрации. Считается, что это вызвало депрессию, и в 1954 году Тьюринг покончил жизнь самоубийством, съев отравленное цианидом яблоко. За пределами академических кругов Тьюринг оставался практически неизвестным, потому что его работа о Второй мировой войне была совершенно секретной. Постепенно слухи о гениальности Тьюринга, его изобретении компьютера и искусственного интеллекта распространились, и после кампании петиций в 2009 году премьер-министр Великобритании Гордон Браун принес публичные извинения, в которых заключался:
«…от имени британского правительства и всех тех, кто живет свободно благодаря работе Алана, я очень горд сказать: мы сожалеем. Ты заслуживаешь гораздо большего».
23 июня 2012 г. – столетие со дня рождения Алана Тьюринга. Я рад сообщить, что наконец-то Тьюринг получает заслуженное признание не только за свою жизненно важную работу на войне, но и за изобретение компьютера — Универсальной машины, — которая изменила современный мир и окажет глубокое влияние на наше будущее.
Выраженные взгляды принадлежат автору (авторам) и не обязательно совпадают с мнением Scientific American.
ОБ АВТОРАХ
Иэн Уотсон – адъюнкт-профессор искусственного интеллекта в Оклендском университете Новой Зеландии, где он занимается исследованиями в области машинного обучения и игрового ИИ. Ян только что написал научно-популярную книгу под названием «Универсальная машина — от зари вычислений до цифрового сознания». Ян ведет блог об истории и будущем вычислений в The Universal Machine. Вы можете следить за ним в твиттере @driwatson, Google+ или Facebook. Следите за новостями Яна Уотсона в Твиттере
Так что же такое универсальный компьютер? Мы немного изменили этот термин. Мы также говорили о том, что значит быть по-настоящему универсальным компьютером или перепрограммируемым компьютером по сравнению с компьютером с фиксированной программой, таким, каким была исходная разностная машина. Так вот, это то, что сделало ENIAC столь же уникальным, как и марка, хотя и в меньшей степени. заключается в том, что они считаются первыми в мире настоящими универсальными компьютерами. Как вы думаете, что значит называться универсальным компьютером? Что ж, универсальный компьютер может имитировать любой компьютер реального мира с бесконечным временем и бесконечной памятью.Итак, если вы представляете себе, что берете свой мобильный телефон или даже что-то маленькое, например, маленькую Raspberry Pi или умные часы. И если бы это был действительно универсальный компьютер, если бы вы предоставили ему достаточно времени и достаточно памяти, он мог бы делать почти все, что мог бы делать любой другой компьютер. Так что сравните это с каким-нибудь суперкомпьютером вроде Beocat, который есть у нас в отделе компьютерных наук здесь, в K-State. Верно, универсальный компьютер может делать все то же, что и Beocat, при наличии достаточного времени и достаточного пространства.
Итак, это подводит нас к Алану Тьюрингу. Так вот, Алан Тьюринг был одним из первых, кто придумал идею действительно универсального компьютера. Теперь, в 1936 году, он предложил идею воображаемого компьютера, и этот воображаемый компьютер был настолько простым, что казалось, что он ничего не может делать правильно. А на самом деле над Аланом Тьюрингом издевались довольно обширно. Просто за то, что придумал эту идею, потому что люди думали, что это просто безумие, что она не сработает. Но теперь мы знаем, что этот воображаемый компьютер известен как машина Тьюринга. Но на самом деле эта машина Тьюринга, эта простая машина, которую он как бы придумал, была способна делать и вычислять любое значение, которое мог бы сделать любой другой компьютер, даже при том, что это было безумно просто. Итак, давайте посмотрим на пример того, как могла бы выглядеть машина Тьюринга, потому что это был воображаемый компьютер, воображаемая машина.
Таким образом, сама машина Тьюринга состоит из бесконечно длинной ленты, и эта лента разделена. На нем есть отдельные квадраты, вроде рулона пленки и классического нецифрового фотоаппарата, но каждый отдельный квадрат, который вы могли бы представлять, был бы либо единицей, либо нулем, либо он мог бы быть пустым, если бы на нем не было ничего. данные в него еще не записаны. Теперь машина фактически работает, перемещаясь вперед и назад по ленте, считывая и записывая единицы и нули в зависимости от значения, которое фактически считывается с ленты. Но как он на самом деле знает, куда идти? Что ж, если вы видите здесь на картинке, в системе также есть этот маленький контроллер.
Теперь на этот контроллер была бы предварительно загружена программа. Итак, мы могли бы написать эту программу, используя эти команды, и это относительно просто, верно? У нас есть восемь различных команд: вправо, влево и вправо, вправо, вправо, ноль, чтение. Таким образом, если этот квадрат равен нулю, или если этот квадрат равен единице, перейдите к шагу x в программе. И тогда у нас также есть просто стрит, переходим к шагу и останавливаемся. Таким образом, сама программа может состоять только из этих восьми шагов, и здесь, в другом видео, мы рассмотрим пример этих восьми шагов в действии. Но действительно важно подчеркнуть, насколько это круто на самом деле, верно? Простота этих восьми основных шагов представляет собой универсальный компьютер. И это универсальное компьютерное право может сделать столько же, сколько суперкомпьютер, такой как Beocat. Таким образом, при наличии достаточного количества времени и памяти машина Тьюринга с этими восемью основными шагами и только чтением и записью единиц и нулей может решить любую задачу.
Читайте также: