Почему компьютер является универсальным устройством обработки информации

Обновлено: 07.07.2024

С незапамятных времен люди пытались найти методы для более эффективного вычисления и обработки данных. Одним из первых вычислительных устройств были счеты, разработанные в Древнем Египте в тринадцатом веке. Счеты представляют собой рамку, состоящую из бусин, нанизанных на проволоку, используемых для сложения, вычитания, деления и умножения. Хотя это примитивное устройство предшествовало карандашу и бумаге, оно все еще используется в двадцать первом веке.

ПЕРВЫЕ СЧЕТНЫЕ МАШИНЫ

Чтобы повысить скорость и точность вычислений, математик Джон Нейпир изобрел логарифмы, которые значительно облегчили арифметические вычисления. Он также изобрел «кости Нейпира» в начале 1600-х годов. Этот инструмент представлял собой таблицу, сделанную из дерева или костей, с надписями умножения. В 1642 году француз Блез Паскаль (1623-1662) изобрел первую счетную машину, названную арифметической машиной. Готфрид Лейбниц (1646–1716) расширил идеи Паскаля и в 1671 году разработал «счетчик шагов», который мог выполнять сложение, вычитание, умножение и деление, а также вычислять квадратные корни.

В 1834 году Чарльз Бэббидж (1791–1871) разработал механическую аналитическую машину, предшественника компьютера. Он был разработан для выполнения сложных вычислений, таких как умножение, деление, сложение и вычитание. Аналитическая машина не была произведена из-за ее механической природы. Механические части работали очень медленно и часто ломались. Хотя эта машина никогда не производилась, она повлияла на конструкцию современных компьютеров. Он включал четыре компонента современных вычислений: ввод, хранение, обработка и вывод. Машина позволяла вводить данные и имела место для хранения данных для обработки. У него также был процессор для вычисления чисел и управления выполнением задач, а также устройство вывода для распечатки информации.

В 1884 году Герман Холлерит (1860–1929) использовал электрические компоненты для разработки компьютера, который правительство США использовало для обработки данных переписи населения США 1890 года. Эта машина получала перфокарты с ручной подачей и позволяла металлическим штифтам проходить через отверстия в чашки, наполненные ртутью, замыкая электрическую цепь. Позже Холлерит усовершенствовал конструкцию и в 1896 году основал компанию Tabulating Machine Company. Позже компания стала называться International Business Machines (IBM) Corporation.

ПЕРВЫЕ СОВРЕМЕННЫЕ КОМПЬЮТЕРЫ

Говарду Эйкену (1900–1973), профессору Гарварда, приписывают создание первого цифрового компьютера под названием Mark I. Эта машина была похожа на аналитическую машину Бэббиджа и была сконструирована из переключателей и реле (металлических стержней, окруженных витки проволоки). На создание этой 5-тонной машины ушло пять лет, поэтому она устарела еще до того, как была завершена.

В Университете штата Айова Джон В. Атанасов (1903–1995) и его аспирант Клиффорд Берри (1918–1963) разработали первый электронный цифровой компьютер специального назначения в 1930-х годах. Компьютер Атанасова-Берри использовал электронные лампы для хранения и арифметики

функции. Усовершенствовав эту конструкцию, Джон Мочли (1907–1980) и Джон Преспер Эккерт-младший (1919–1995) из Пенсильванского университета разработали в 1945 году первый крупномасштабный электронный цифровой компьютер, используемый для общих целей. электронный числовой интегратор и компьютер, или ENIAC, весил 30 тонн и занимал площадь 1500 квадратных футов. Эта огромная машина использовала 18 000 электронных ламп для хранения и арифметических вычислений.

Экерт и Мочли основали собственную компанию, которая позже стала известна как Remington Rand Corporation, и разработали универсальный автоматический компьютер (UNIVAC) в 1951 году. UNIVAC стал первым коммерческим компьютером, доступным для бизнеса и промышленности. Эта машина использовала магнитную ленту для хранения ввода и вывода вместо перфокарт, которые использовались в предыдущих машинах. IBM извлекла выгоду из концепции коммерческих приложений и разработала компьютерные системы IBM 701 и IBM 752. Из-за меньшего размера по сравнению с UNIVAC I модели IBM заняли более 70% рынка промышленных компьютеров.

Транзисторы заменили электронные лампы и положили начало эволюции компьютеров второго поколения. Транзисторы,

изобретенные в 1947 году, они были дешевле электронных ламп, выделяли меньше тепла и производили более надежные компьютеры. Компьютеры на транзисторах пользовались большим спросом из-за их небольшого размера, меньшей стоимости и большей надежности.

По мере роста спроса на компьютеры программисты были поглощены утомительным процессом программирования компьютеров для работы. Компьютерные программисты использовали машинный язык, чтобы давать инструкции компьютеру. Машинный язык — это двоичный код (состоящий из нулей и единиц), который компьютер понимает напрямую.Каждая отдельная модель компьютера имела уникальный язык программирования. Например, у UNIVAC был другой машинный язык, чем тот, который использовался в IBM 752. Чтобы облегчить задачу программирования компьютеров, машинный язык был заменен языком ассемблера. Программисты использовали ассемблеры для преобразования или перевода англоязычного кода, разработанного с использованием языка ассемблера, в машинный язык. Этот низкоуровневый язык повысил скорость написания программ.

Использование интегральных схем улучшило развитие компьютеров, что привело к появлению компьютеров третьего поколения. В интегральных схемах, разработанных в 1958 году, использовались миниатюрные транзисторы, которые монтировались на маленькие кремниевые чипы длиной около четверти дюйма с каждой стороны. Эти микрочипы позволили ученым разработать еще более компактные, быстрые и надежные компьютеры. IBM использовала микрочипы для разработки компьютеров серии 360. Вместо перфокарт пользователи взаимодействовали со своими компьютерами с помощью клавиатур, мониторов и операционных систем.

В эпоху третьего поколения появились языки программирования высокого уровня. В то время как компьютеры третьего поколения выполняли более сложные манипуляции с данными, общение с компьютерами также усложнялось. Языки программирования, такие как COBOL и FORTRAN, были разработаны в 1950-х годах, чтобы упростить программирование компьютера. Эти языки высокого уровня использовали компиляторы или интерпретаторы для преобразования кода, похожего на английский, в машинный язык.

КОМПЬЮТЕРЫ ЧЕТВЕРТОГО ПОКОЛЕНИЯ

Компьютеры четвертого поколения появились благодаря развитию микропроцессора. Названный полупроводником, этот процессор был произведен в 1971 году компанией Intel. Полупроводник представлял собой крупномасштабную интегральную схему, содержащую тысячи транзисторов на одном кристалле. Разработка этого чипа привела к созданию первого персонального компьютера. С этим изобретением компьютеры стали использоваться не только крупными предприятиями и военными, но и малыми предприятиями и домашними хозяйствами.

IBM представила свой первый домашний компьютер в 1981 году, а Apple разработала домашний компьютер Macintosh в 1984 году. Микросхема Intel 4004 объединяет все компоненты компьютера в один крошечный чип. Это нововведение в конечном итоге привело к разработке портативных устройств. Карманные устройства — это портативные компьютеры, обладающие многими возможностями настольного компьютера. Одним из популярных портативных устройств является персональный цифровой помощник, который позволяет пользователю планировать и систематизировать информацию.

ИНТЕРНЕТ И ВСЕМИРНАЯ ПАУТИНА

Мощные возможности микропроцессоров позволили небольшим компьютерам объединяться в сети или Интернет. Интернет, концептуализированный в конце 1960-х годов исследователями из Агентства перспективных исследовательских проектов Министерства обороны США, представляет собой сеть компьютерных сетей, обеспечивающих общение между пользователями компьютеров. Интернет упростил использование электронной почты, которая является широко используемой формой связи.

Интернет был улучшен за счет всемирной паутины (WWW), которая позволяет пользователям компьютеров искать, просматривать и распространять информацию по множеству тем с веб-сайтов. WWW был разработан в 1990 году Тимом Бернерсом-Ли (1955 – ). Интернет в сочетании с Всемирной паутиной коренным образом изменил способы общения, распространения и обработки информации в промышленно развитых странах.

КОМПЬЮТЕРЫ ПЯТОГО ПОКОЛЕНИЯ

Вычислительные устройства пятого поколения в настоящее время находятся в стадии разработки. В центре внимания этого поколения — заставить компьютеры вести себя как люди. Это явление было названо искусственным интеллектом Джоном Маккарти (1927-) в Массачусетском технологическом институте в 1957 году. Область искусственного интеллекта включает игры, экспертные системы, естественные языки, нейронные сети и робототехнику. Игры включают в себя создание игр, которые позволяют пользователям играть против компьютера. Экспертные системы — это компьютерные приложения, которые выполняют задачи человека-эксперта, такие как диагностика болезни. Естественные языки позволяют компьютерам понимать естественные человеческие языки, такие как английский или китайский. Нейронные сети пытаются функционировать как мозг человека или животного. Робототехника включает в себя создание компьютеров, которые могут использовать человеческие чувства, такие как зрение и слух.

Несмотря на то, что ученым очень трудно заставить компьютеры вести себя и думать как люди, в этой области достигнуты определенные успехи. Что касается игр, программисты разработали компьютерные игры, которые могут «перехитрить» людей. В области естественных языков было разработано программное обеспечение для распознавания голоса, позволяющее преобразовывать устные слова в письменные. Это позволяет пользователям говорить с компьютером, а компьютер в свою очередь диктует то, что пользователь говорит в виде слов на экране.

Обработка информации или данных стала синонимом компьютеров. Развитие компьютеров, Интернета и WWW значительно улучшило способы обработки информации.Эти инструменты предоставили обществу больше возможностей для обработки информации, чем когда-либо прежде. Поскольку постоянно меняющийся мир продолжает развиваться, можно быть уверенным, что скоро последуют новые инновации в области обработки информации.

библиография

ПЕРВЫЕ СЧЕТНЫЕ МАШИНЫ

ПЕРВЫЕ СОВРЕМЕННЫЕ КОМПЬЮТЕРЫ

По мере роста спроса на компьютеры программисты были поглощены утомительным процессом программирования компьютеров для работы.Компьютерные программисты использовали машинный язык, чтобы давать инструкции компьютеру. Машинный язык — это двоичный код (состоящий из нулей и единиц), который компьютер понимает напрямую. Каждая отдельная модель компьютера имела уникальный язык программирования. Например, у UNIVAC был другой машинный язык, чем тот, который использовался в IBM 752. Чтобы облегчить задачу программирования компьютеров, машинный язык был заменен языком ассемблера. Программисты использовали ассемблеры для преобразования или перевода англоязычного кода, разработанного с использованием языка ассемблера, в машинный язык. Этот низкоуровневый язык повысил скорость написания программ.

КОМПЬЮТЕРЫ ЧЕТВЕРТОГО ПОКОЛЕНИЯ

ИНТЕРНЕТ И ВСЕМИРНАЯ ПАУТИНА

КОМПЬЮТЕРЫ ПЯТОГО ПОКОЛЕНИЯ

Обработка информации или данных стала синонимом компьютеров. Развитие компьютеров, Интернета и WWW значительно улучшило способы обработки информации. Эти инструменты предоставили обществу больше возможностей для обработки информации, чем когда-либо прежде. Поскольку постоянно меняющийся мир продолжает развиваться, можно быть уверенным, что скоро последуют новые инновации в области обработки информации.

библиография

Алан Тьюринг, будучи студентом-математиком Кембриджского университета, был вдохновлен формалистической программой немецкого математика Давида Гильберта, которая стремилась продемонстрировать, что любая математическая задача потенциально может быть решена с помощью алгоритма, то есть с помощью чисто механического процесса. . Тьюринг интерпретировал это как вычислительную машину и намеревался спроектировать машину, способную решать все математические задачи, но в процессе он доказал в своей основополагающей статье «О вычислимых числах с приложением к Entscheidungsproblem [ «Проблема остановки»]» (1936 г.), что такой универсальный математический решатель никогда не мог существовать.

Чтобы спроектировать свою машину (известную потомкам как «машина Тьюринга»), ему нужно было найти однозначное определение сущности компьютера. При этом Тьюринг очень подробно разработал основные концепции универсальной вычислительной машины, то есть вычислительной машины, которая могла бы, по крайней мере теоретически, делать все то же, что и вычислительное устройство специального назначения. В частности, он не ограничивался бы арифметикой. Внутренние состояния машины могут представлять числа, но с таким же успехом они могут представлять логические значения или буквы. На самом деле Тьюринг считал, что все можно представить символически, даже абстрактные психические состояния, и он был одним из первых сторонников теории искусственного интеллекта, согласно которой компьютеры потенциально могут «думать».

Работа Тьюринга до этого момента была полностью абстрактной, полностью теоретической демонстрацией. Тем не менее, он с самого начала дал понять, что его результаты подразумевают возможность создания машины того типа, который он описал. Его работа настолько хорошо описывала абстрактную сущность любого вычислительного устройства, что создать его было непросто.

Работа Тьюринга оказала непосредственное влияние только на небольшое число ученых в нескольких университетах, которые интересовались концепцией вычислительной техники. Это не оказало непосредственного влияния на растущую индустрию бизнес-машин, все из которых были устройствами специального назначения. Но для тех немногих, кому это было интересно, работа Тьюринга послужила источником вдохновения для создания чего-то, о чем большая часть мира даже не подозревала: универсальной вычислительной машины.

Новаторская работа

Компьютер Атанасова-Берри

Принято считать, что первыми электронными цифровыми компьютерами были Colossus, построенный в Англии в 1943 году, и ENIAC, построенный в США в 1945 году. Однако на самом деле первый электронный компьютер специального назначения мог быть изобретен Джон Винсент Атанасов, физик и математик из Колледжа штата Айова (ныне Университет штата Айова), в 1937–1942 годах. (Атанасов также утверждал, что изобрел термин аналоговый компьютер для описания таких машин, как дифференциальный анализатор Ванневара Буша.) Вместе со своим ассистентом Клиффордом Э. Берри Атанасов построил в 1939 году успешный небольшой прототип для этой цели. тестирования двух основных идей его конструкции: конденсаторов для хранения данных в двоичной форме и электронных логических схем для сложения и вычитания. Затем они приступили к проектированию и созданию более крупного и универсального компьютера, известного как компьютер Атанасова-Берри, или ABC.

Клиффорд Берри и компьютер Атанасова-Берри. Азбука, с. 1942 г., возможно, был первым электронным цифровым компьютером.

Различные компоненты ABC проектировались и производились с 1939 по 1942 год, но с началом Второй мировой войны разработка была прекращена. В ABC было около 300 электронных ламп для управления и арифметических вычислений, использования двоичных чисел, логических операций (вместо прямого счета), конденсаторов памяти и перфокарт в качестве устройств ввода-вывода. (По приглашению Атанасова другой пионер компьютеров, Джон Мочли, остановился у него дома, и ему в течение нескольких дней в июне 1941 года бесплатно демонстрировались его работы. Подробнее о последствиях этого визита см. см. BTW: Computer патентные войны.)

Первая компьютерная сеть

В период с 1940 по 1946 год Джордж Стибиц и его команда из Bell Laboratories построили серию машин с телефонными технологиями, то есть с использованием электромеханических реле. Это были первые машины, которые обслуживали более одного пользователя, и первые, которые работали удаленно по телефонным линиям.Однако, поскольку они были основаны на медленных механических реле, а не на электронных переключателях, они устарели почти сразу после их создания.

Конрад Цузе

Тем временем в Германии инженер Конрад Цузе думал о вычислительных машинах. В 1937 году производитель калькуляторов сообщил ему, что эта область зашла в тупик и что все вычислительные проблемы уже решены. Однако Цузе имел в виду кое-что другое.

Во-первых, Цузе с самого начала работал в двоичном формате. Все его прототипы машин, построенные в 1936 году, использовали двоичное представление для упрощения конструкции. Это имело дополнительное преимущество, делая связь с логикой более ясной, и Цузе разработал детали того, как логические операции (например, И, ИЛИ и НЕ) могут быть отображены на схеме компьютерных схем. (Английский математик Джордж Буль показал связь между логикой и математикой в середине 19-го века, разработав алгебру логики, теперь известную как булева алгебра.) Цузе также потратил больше времени, чем его предшественники и современники, на разработку программного обеспечения для своего компьютера, языка в котором он должен быть запрограммирован. (Его вклад в программирование рассмотрен в разделе «Языки программирования».) Хотя все его ранние довоенные машины были на самом деле калькуляторами, а не компьютерами, его Z3, завершенный в декабре 1941 г. ), был первым процессором с программным управлением.

Поскольку вся работа Цузе выполнялась в относительной изоляции, он мало знал о работе с компьютерами в США и Англии, а когда началась война, изоляция стала полной.

В следующем разделе "Развитие во время Второй мировой войны" рассматривается разработка в 1940-х годах первых полнофункциональных цифровых компьютеров.

События во время Второй мировой войны

Колосс

Свидетельствуйте о работе Colossus, первого в мире программируемого электронного компьютера с помощью копии

Требования войны дали толчок и финансирование для компьютерных исследований. Например, в Британии толчком стал взлом кодов. Проект «Ультра» финансировался в условиях большой секретности для разработки технологии, необходимой для взлома шифров и кодов, производимых немецкими электромеханическими устройствами, известными как «Энигма» и «Гехаймшрайбер» («Секретный писатель»). Первая из серии важных машин для взлома кодов, Colossus, также известная как Mark I, была построена под руководством сэра Томаса Флауэрса и доставлена в декабре 1943 года для операции по взлому кодов в Блетчли-Парке, правительственном исследовательском центре на севере США. Лондона. Для вычислений использовалось около 1800 электронных ламп. В течение следующих двух лет были построены более крупные и сложные версии.

В проекте Ultra участвовал одаренный математик, работавший в Блетчли-Парк, и знакомый с кодами. Алан Тьюринг, который ранее сформулировал концепцию универсального вычислительного устройства (описанную в разделе «Машина Тьюринга»), возможно, продвинул проект дальше в направлении создания универсального устройства, чем изначально предполагалось его правительством. Защита интересов Тьюринга помогла правительству сохранить поддержку проекта.

Несмотря на то, что в нем отсутствовали некоторые характеристики, которые теперь ассоциируются с компьютерами, Colossus можно с полным правом назвать первым электронным цифровым компьютером, и он, безусловно, был ключевой ступенью в развитии современного компьютера. Хотя Colossus был разработан для выполнения конкретных криптографических вычислений, его можно было использовать и для более общих целей. Его конструкция положила начало массовому использованию электроники в вычислениях и воплотила понимание Флауэрсом важности электронного хранения данных внутри машины. Операция в Блетчли предвосхитила современный центр обработки данных.

Компьютер Colossus в Блетчли-парке, Бакингемшир, Англия, около 1943 года. Финансирование этой машины для взлома кодов поступило от проекта Ultra.

Колосс преуспел в достижении намеченной цели: немецкие сообщения, которые он помог расшифровать, содержали информацию о немецких боевых порядках, припасах и личном составе; это также подтвердило, что кампания обмана союзников, операция «Стойкость», работала.

Серия компьютеров Colossus была разобрана после войны, и большая часть информации о них оставалась засекреченной до 1990-х годов. В 1996 году базовая машина Colossus была перестроена и запущена в Блетчли-парке.

Z4

В Германии Конрад Цузе начал строительство Z4 в 1943 году при финансовой поддержке Министерства авиации.Как и его Z3 (описанный в разделе Конрад Цузе), Z4 использовал электромеханические реле, отчасти из-за сложности приобретения примерно 2000 необходимых электронных ламп в Германии военного времени. Z4 был эвакуирован из Берлина в начале 1945 года и в конце концов оказался в Хинтерштайне, небольшой деревне в Баварских Альпах, где оставался до тех пор, пока Цузе не привез его в Федеральный технический институт в Цюрихе, Швейцария, для ремонта в 1950 году. чтобы продолжить разработку аппаратного обеспечения, Цузе добился ряда успехов в разработке программного обеспечения.

Использование Zuse представления чисел с плавающей запятой — значащие цифры, известные как мантисса, хранятся отдельно от указателя на десятичную точку, известную как экспонента, что позволяет обрабатывать очень большой диапазон чисел — было намного опередил свое время. Вдобавок Цузе разработал богатый набор инструкций, правильно обрабатывал бесконечные значения и включил «без операции», то есть инструкцию, которая ничего не делала. Только значительный опыт программирования может показать необходимость в чем-то настолько бесполезном.

Программа Z4 была пробита на использованной кинопленке и была отделена от механической памяти для данных (другими словами, не было сохраненной программы). Машина была относительно надежна (обычно работала всю ночь без присмотра), но не имела возможности принимать решения. Сложение занимало от 0,5 до 1,25 секунды, умножение — 3,5 секунды.

Эта статья является частью эксклюзивной серии Critique, посвященной биографическому фильму Алана Тьюринга «Игра в имитацию».

Введение

Разум — это система обработки информации. Система обработки информации — это все, что преобразует информацию в информацию. Через наши глаза, уши и другие органы чувств мы загружаем информацию о внешнем мире. Наша центральная нервная система обрабатывает эту информацию. Затем он выводит убеждения, которые, в свою очередь, приводят к действию.

Ваш компьютер представляет собой систему обработки информации. Информация загружается, конвертируется, а затем загружается. То же самое верно для всех компьютеров. В этом отношении компьютеры не так уж отличаются от человеческого разума.

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

Никто не сделал для демонстрации этого больше, чем Алан Тьюринг. И все же никто не сыграл большей роли, чем Тьюринг, в разработке современного компьютера. Как мы увидим, эти два достижения Тьюринга — две стороны одной медали.

Эта статья состоит из двух частей. В первой части мы опишем тьюринговский анализ вычислимости. Этот анализ является основой современной компьютерной науки. Во второй части мы обсудим отношение анализа Тьюринга к вопросу: мы компьютеры?

Часть I: Тьюринговский анализ вычислимости

Тьюринг сам не создавал физический компьютер; он также не создал компьютерную программу. То, что он сделал, было гораздо важнее. Он создал мета-программу — схему создания программ, известную как Универсальная машина Тьюринга. Универсальная машина Тьюринга — это просто очень точное описание того, что значит вычислять решение проблемы.

Не все случаи нахождения решения являются случаями вычисления решения. Решение, известное на основе интуиции или неформальных рассуждений, не вычисляется. Чтобы вычислить решение, нужно использовать алгоритм для его идентификации.

Алгоритм – это механическая процедура. В начальной школе вы изучали механические процедуры сложения и умножения многозначных чисел. Это примеры алгоритмов.

Алгоритмы умножения и сложения связаны не с числами или математическими операциями, а с физическими надписями — не с числом 5 или операцией сложения, а с соответствующими выражениями. В соответствии с этими алгоритмами допустимость данной надписи или последовательности надписей зависит от ее формы, а не от ее значения. Алгоритм имеет дело с чувствительностью к форме символа, а не с чувствительностью к значению символа. По этой причине машины могут их реализовывать и тем самым решать арифметические задачи.

Все алгоритмы связаны с геометрическими или строго физическими свойствами объектов. Никого не интересуют их семантические свойства — другими словами, их значения. По этой причине алгоритмы могут быть реализованы машинами.

В начале 20 века были изобретены алгоритмы для вывода утверждений из других утверждений. Так была создана дисциплина математическая логика, цель которой — механизировать выведение выводов. Информатика выросла из математической логики.С появлением информатики возникли вопросы, как практические, так и философские, относительно сходства или отсутствия сходства между разумом и компьютером.

Проведя точный и тщательный анализ концепции вычислений, Алан Тьюринг прояснил, как разрешать многие из этих противоречий. Суть анализа Тьюринга можно выразить одним предложением: если проблему можно решить механическим способом, то решение является результатом рекурсивной функции.

Начнем с того, что это значит. Тогда мы скажем, почему это правда. И, наконец, во второй части мы обсудим, как это влияет на вопрос: мы компьютеры?

Объяснение анализа Тьюринга

Давайте начнем с определения термина "рекурсивная функция". Во-первых, рекурсивная функция — это математическая функция. Функция в математическом смысле — это правило, которое назначает выходы входам. Рассмотрим функцию F(x)=x+1. Эта функция присваивает 2 1, 3 2 и так далее. Другими словами, 2 — это выход, если 1 — это вход, и 3 — это выход, если 2 — это вход.

Функция не обязана присваивать числа числам. На самом деле, великие инновации в математической логике, лежащие в основе информатики, стали возможными благодаря открытию того, что некоторые из наиболее важных функций не имеют ничего общего с числами. В эту категорию попадают функции, с которыми имеет дело булевская алгебра, как и функции, с которыми имеет дело исчисление высказываний. Обе дисциплины необходимы для информатики.

Функция не может назначать разные выходы для одного входа. В остальном ограничений на то, что функция может назначать, нет.

рекурсивная функция — это функция, определенная для каждого из своих собственных выходных данных. Рассмотрим ряд: 2, 4, 16, 256, 65 536… Этот ряд генерируется рекурсивной функцией, а именно: F(1)=2 и F(n+1)=n 2 . Эта функция присваивает 2 числу, соответствующему первой позиции в ряду — это число, конечно, является номером один, — и, если она присваивает n числу, соответствующему данной позиции в ряду, то она присваивает n 2 число, соответствующее следующей позиции.

Для более простого примера ряд 1, 2, 3,… создается рекурсивной функцией: F(1)=1 и F(n+1)=1+F(n).

Рекурсивная функция определяется (1) правилом, которое явно присваивает определенный результат начальному входу, а также (2) правилом генерирования вывода для любого заданного входа, кроме начального входа, на основе вывода к предыдущему вводу.

Арифметика основана на следующих рекурсиях:

При наличии достаточного количества времени любую арифметическую задачу можно решить с помощью этих рекурсий. В случае, когда 0 является релевантным операндом, ответ дается явно. В противном случае ответ получается повторением правила, содержащегося во второй части соответствующей рекурсии.

Благодаря (1)-(3) арифметика вообще не требует размышлений. Таким образом, можно создать машины, решающие арифметические задачи столь же бездумно, но и безошибочно, как машины, создающие колпаки.

Везде, где есть рекурсивная функция, есть механическая процедура принятия решения.

Согласно Тьюрингу, верно и обратное: везде, где есть процедура принятия решения, есть и рекурсивная функция. Другими словами, если проблема может быть решена механическим способом, решение является результатом рекурсивной функции.

Оценка анализа Тьюринга

Обоснование утверждения Тьюринга заключается не в формальном доказательстве, а в соображениях философского характера, которые мы сейчас изложим.

Во-первых, список правильных арифметических утверждений, например. «5+3=8» и «7 2 =49» не являются процедурой принятия решения. Такой список предполагает существующий способ получения соответствующих знаний. Следовательно, в той мере, в какой такой список доступен, процедура принятия решения не может добавить к тому, что мы знаем. Но процедура принятия решения, которая не может добавить к тому, что мы знаем, вообще не является процедурой принятия решения.

Что еще более важно, процедура принятия решения по своей природе является общей. Список истин — это запись ранее существовавших знаний. Поскольку процедура принятия решения — это способ приобретения новых знаний, никакой список истин не является процедурой принятия решения. Из этого следует, что процедура принятия решения должна применяться к бесконечному количеству случаев, которые в ней явно не упоминаются. Это означает, что любая данная процедура принятия решения должна содержать условную информацию: информацию о том, что если выполняется то-то и то-то, то то-то и то-то также выполняется.

Есть два способа получения новой информации. Один из них — использование наших чувств, то есть наблюдение за миром. Другой — путем рассуждений, то есть выводов из того, что мы уже знаем. Используя свои чувства для приобретения знаний, человек, очевидно, не использует процедуру принятия решения.Таким образом, первый способ не имеет значения в данном контексте, это второй способ, который мы должны рассмотреть.

Второй путь обязательно предполагает знание условных истин: истин вида если так-то и так-то имеет место, то так-то и так-то также имеет место. (например, если Билл находится в Париже, то он не в Мадриде).

Поскольку процедуры принятия решений позволяют нам добавлять что-то к тому, что мы знаем, это происходит благодаря воплощению условных истин. Но процедуры-решения не могут быть строго условными, поскольку такие процедуры, что имеет место то-то и то-то, а не просто то-то и то-то, если то-то и то-то кейс. Например, (1) явно говорит нам, что 2+0=2, и неявно говорит нам, что 2+6=8.

В той мере, в какой данная процедура принятия решения применима к бесконечному количеству случаев, она должна быть условной. (Рассмотрим вторую часть (1), которая говорит нам, что если 2+5=7, то 2+(5+1)=8.)

В той мере, в какой процедура принятия решения применима к каким-либо случаям вообще, она должна быть безусловной. (Рассмотрите первую часть (1), которая говорит нам, что 2+0=2.)

Но это также означает, что процедура принятия решения должна подсказать вам, как генерировать новое знание на основе ассерторической информации, которую она вам дает; а это значит, что такая процедура должна содержать условную информацию. (Учтите, что две части (3), взятые вместе, позволяют вычислить любой показатель, хотя первая часть позволяет вычислить только один, а вторая часть не позволяет вычислить любой.)

Поэтому процедуре принятия решения присуще то, что любая такая процедура содержит два компонента:

(a) базовая оговорка о том, что имеет место то-то и то-то; и

(b) условное предложение (обычно называемое индуктивным предложением, где «индуктивное» является синонимом «рекурсивного») в том смысле, что если так-то и так-то, то так-то и так-то тоже.

Любое выражение, имеющее такую структуру из двух частей, в силу самого факта является рекурсией. Таким образом, там, где есть процедура принятия решения, есть и рекурсия; и, как отмечалось ранее, там, где есть рекурсия, есть и процедура принятия решения.

Так что Тьюринг прав. Проблема может быть решена механическим способом — ее решение может быть вычислено, другими словами — тогда и только тогда, когда решение является результатом рекурсивной функции.

Концепция машины Тьюринга

Давайте теперь обсудим гениальный способ Тьюринга проиллюстрировать эти довольно трудные для понимания моменты. Представьте бесконечно длинную бумажную ленту, разделенную на квадраты. Эта лента проходит через машину по одному квадрату за раз. Некоторые квадраты пусты; на других есть маркировка. Когда заданный квадрат находится внутри машины, машина сканирует его. Если на квадрате есть маркировка, автомат может:

(1) Сотрите эту маркировку,

(2) Добавить еще одну отметку,

(3) вообще ничего не делать или

(4) Переместиться на один или несколько квадратов вправо или влево.

Если квадрат пуст, машина может:

(A) Напишите на нем символ;

(B) Ничего не делать; или

Поведение машины предопределено ее программой. Эта программа состоит из инструкций о том, что если состояние данного квадрата такое-то и такое-то, то машина должна делать то-то и то-то.

В этой гипотетической ситуации есть два существенных факта: во-первых, машина не может ничего сделать, если ей не будут переданы данные; и, во-вторых, поведение машины является функцией только состояния квадрата, который она сканирует в данный момент, в сочетании с ее программой.

Состояние ленты перед сканированием соответствует базовому предложению рекурсии, а программа машины соответствует индуктивному предложению.

Тьюринг доказал, что при наличии любой проблемы, которую мы интуитивно считаем возможной решить с помощью процедуры принятия решения, только что описанная машина может решить ее.

Машина только что описанного типа, ограниченная одной программой, называется Машиной Тьюринга. Такая машина, на которой может выполняться любая программа, называется Универсальной машиной Тьюринга. Если данная проблема может быть решена механически, она может быть решена соответствующим образом запрограммированной машиной Тьюринга и, таким образом, является «разрешимой по Тьюрингу».

Неразрешимая проблема Тьюринга

Тьюринг доказал, что не все проблемы разрешимы по Тьюрингу. Рассмотрим вопрос:

(T) Все ли проблемы разрешимы по Тьюрингу?

В качестве аргумента предположим, что ответ "да". В этом случае существует программа P, которую можно запустить на машине Тьюринга и которая обладает следующим свойством: при любой программе F и любом вводе I, P может определить, «остановится» ли машина Тьюринга, выполняющая F, при вводе данных. я.

Учитывая существование P, следует, что существует программа Q такая, что для любой программы F Q может определить, остановится ли F, если F запустит саму F.

Учитывая существование Q, следует, что существует программа R такая, что:

(1) Для любой программы F, R работает вечно, если, согласно Q, F останавливается, если F работает сама; а также такое, что

(2) R останавливается, если, согласно Q, F работает вечно, если F работает сама.

Предположим, что R работает сам по себе. Есть ровно два возможных случая для рассмотрения.

Случай номер 1. Предположим, согласно Q, R останавливается, если R запускается сам. В этом случае по (1) R работает вечно.

Случай номер 2. Предположим, что согласно Q, R работает вечно, если R работает сам. В этом случае по (2) R останавливается.

В первом случае R работает вечно, если R останавливается. Во втором R останавливается, если R работает вечно. Таким образом, если R работает сам по себе, он останавливается тогда и только тогда, когда он не останавливается. Поскольку это невозможно, не может быть такой программы, как R. Поскольку R существует, если существует Q, Q не существует; и поскольку Q существует, если существует P, то P не существует. Таким образом, невозможно вычислить решение «проблемы остановки».

Это не означает, что эту проблему невозможно решить, просто нет механического способа сделать это.

Часть 2. Философские выводы

Компьютер по определению является механическим решением проблем. Сказать, что проблему можно решить механически, значит сказать, что для ее решения не требуется никакого мышления. Таким образом, если это может сделать компьютер, мысль для этого не требуется. Механические решатели проблем — не мыслители; они мыслители-прокси.

«Но если компьютеры не думают, — возразят, — значит, они не решают проблем».

Компьютеры не думают и не решают проблемы. Механический «решатель проблем» – это человек, не умеющий решать проблемы, чье поведение позволяет разумному наблюдателю легко решать сложные проблемы.

Предположим, что 3+5= введено в корректно работающее вычислительное устройство. Это устройство устроено так, что на основе физических характеристик этого входа оно выдает 8. Если бы на основе значения этого входа оно решал, что выводить, это вообще не было бы вычисляющим устройством. Точно так же, поскольку это является устройством, оно слепо к значению как ввода, так и вывода. Следовательно, он никак не может осознавать тот факт, что вывод соответствовал по смыслу вводу, и, следовательно, ни в каком буквальном смысле ничего не решил. Он добился того, чтобы облегчить решение рассматриваемой проблемы тому, кто разбирается в вводе и выводе.

Сам Тьюринг прекрасно осознавал различие между существами, такими как мы, которые действительно решают проблемы, и существами, такими как машины Тьюринга, которые просто имитируют поведение при решении проблем. В своей знаменательной статье О вычислимых числах, часть 1 которой является кратким изложением, Тьюринг указывает, что под «компьютером» он подразумевает человека, который вычисляет — тот, кто использует процедуру принятия решения для решения проблемы.

Разум необходим для создания алгоритмов, а не для их реализации. Сама цель алгоритма состоит в том, чтобы сделать мысли ненужными. Мы используем алгоритмы для выполнения арифметических операций именно потому, что хотим как можно меньше думать об арифметике.

Следствием того, что мы можем создавать алгоритмы, является то, что мы можем их оценивать. Имея алгоритм, мы можем определить, дает ли он правильные результаты. Нет такой программы, легитимность которой мы не могли бы подвергнуть сомнению. Компьютер не может подвергать сомнению свою собственную программу; ибо компьютер не может отклонить свою собственную программу. Компьютер мог бы сделать это только в том случае, если бы его программа позволяла ему это делать. Но если компьютер отвергает свою программу на основании этой программы, он следует этой программе и, следовательно, не отвергает ее.

Заметим, что этот аргумент имеет некоторое сходство с доказательством Тьюринга, что не все проблемы разрешимы по Тьюрингу. Наводит на мысль, что Тьюринг включил это доказательство в ту же статью, где он описывает машины Тьюринга. Безусловно, у Тьюринга были причины строго дискурсивного характера для этого. Но его решение включить его, возможно, отражало желание с его стороны прояснить, что машины Тьюринга просто моделируют мысли. Если бы он высказался по этому поводу более четко, то полвека психологических исследований, возможно, не были бы потрачены впустую на трагически ошибочное представление о том, что мозг — это цифровой компьютер.

Читайте также: