# data[].attributes.headline
1936: Винахід машини Тьюрінга: 

# data[].attributes.subject
1936: Винахід машини Тьюрінга: 

# data[].attributes.body
Алан Тьюрінг формулює концепцію універсальної машини Тьюрінга, що лягла в основу сучасних комп'ютерів і оперативної пам'яті.

# data[].attributes.attachment_link.readable_text
Художественное представление машины Тьюринга

Маши́на Тью́ринга (сокр. МТ) - абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма.

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

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

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

В состав машины Тьюринга входит неограниченная в обе стороны лента (возможны машины Тьюринга, которые имеют несколько бесконечных лент), разделённая на ячейки, и управляющее устройство (также называется головкой записи-чтения ( ГЗЧ)), способное находиться в одном из множества состояний. Число возможных состояний управляющего устройства конечно и точно задано.

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

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

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

Конкретная машина Тьюринга задаётся перечислением букв алфавита A, множеством состояний Q и набором правил перехода, по которым работает машина. Они имеют вид: q ia j→q i1a j1d k (если головка находится в состоянии q i, а в обозреваемой ячейке записана буква a j, то головка переходит в состояние q i1, в ячейку вместо a j записывается a j1, головка делает движение d k, которое имеет три варианта: на ячейку влево (L), на ячейку вправо (R), остаться на месте (N)). Для каждой возможной конфигурации <q i, a j> имеется ровно одно правило (для недетерминированной машины Тьюринга может быть большее количество правил). Правил нет только для заключительного состояния, попав в которое, машина останавливается. Кроме того, необходимо указать начальное и конечное состояния, начальную конфигурацию на ленте и расположение головки машины.

Пример машины Тьюринга для умножения чисел в унарной системе счисления. Запись правила перехода "q ia j→q i1a j1R/L/N" следует понимать так: q i - состояние, при котором выполняется это правило, a j - данные в ячейке, в которой находится головка, q i1 - состояние, в которое нужно перейти, a j1 - что нужно записать в ячейку, R/L/N - команда на перемещение.

Машина работает по следующему набору правил:

Описание состояний:

Переносим все "1" из первого числа в результат

ищем "1" слева, заменяем её на "а" и переходим в состояние q4.

В случае, если "1" закончились, находим "*" и переходим в состояние q6

Обрабатываем каждый разряд второго числа

ищем "1" или "=" справа,

при нахождении "1" заменяем его на "а" и переходим в состояние q2

при нахождении "=" переходим в состояние q8

Умножим с помощью МТ 3 на 2 в единичной системе. В протоколе указаны начальное и конечное состояния МТ, начальная конфигурация на ленте и расположение головки машины (подчёркнутый символ).

Начало. Находимся в состоянии q ₀, ввели в машину данные: *111x11=*, головка машины располагается на первом символе *.

1-й шаг. Смотрим по таблице правил, что будет делать машина, находясь в состоянии q ₀ и над символом "*". Это правило из 1-го столбца 5-й строки - q ₀*→q ₀*R. Это значит, что мы переходим в состояние q ₀ (то есть не меняем его), символ станет "*" (то есть не изменится) и смещаемся по введённому нами тексту "*111x11=*" вправо на одну позицию (R), то есть на 1-й символ 1. В свою очередь, состояние q ₀1 (1-й столбец 1-я строка) обрабатывается правилом q ₀1→q ₀ 1R. То есть снова происходит просто переход вправо на 1 позицию. Так происходит, пока мы не станем на символ "х". И так далее: берём состояние (индекс при q), берём символ, на котором стоим (подчёркнутый символ), соединяем их и смотрим обработку полученной комбинации по таблице правил.

Простыми словами, алгоритм умножения следующий: помечаем 1-ю единицу 2-го множителя, заменяя её на букву "а", и переносим весь 1-й множитель за знак равенства. Перенос производится путём поочерёдной замены единиц 1-го множителя на "а" и дописывания такого же количества единиц в конце строки (слева от крайнего правого "*"). Затем меняем все "а" до знака умножения "х" обратно на единицы. И цикл повторяется. Действительно, ведь A умножить на В можно представить как А+А+А В раз. Помечаем теперь 2-ю единицу 2-го множителя буквой "а" и снова переносим единицы. Когда до знака "=" не окажется единиц - значит, умножение завершено.

Протокол

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

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

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

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

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

На машине Тьюринга можно имитировать машину Поста, нормальные алгоритмы Маркова и любую программу для обычных компьютеров, преобразующую входные данные в выходные по какому-либо алгоритму. В свою очередь, на различных абстрактных исполнителях можно имитировать Машину Тьюринга. Исполнители, для которых это возможно, называются полными по Тьюрингу (Turing complete).

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

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

Машина Тьюринга, работающая на полубесконечной ленте

В качестве примера такого сведения рассмотрим следующую теорему: Для любой машины Тьюринга существует эквивалентная машина Тьюринга, работающая на полубесконечной ленте (то есть на ленте, бесконечной в одну сторону).

Рассмотрим доказательство, приведённое Ю. Г. Карповым в книге "Теория автоматов". Доказательство этой теоремы конструктивное, то есть мы дадим алгоритм, по которому для любой машины Тьюринга может быть построена эквивалентная машина Тьюринга с объявленным свойством. Во-первых, произвольно занумеруем ячейки рабочей ленты МТ, то есть определим новое расположение информации на ленте:

Затем перенумеруем ячейки, причём будем считать, что символ "*" не содержится в словаре МТ:

Наконец, изменим машину Тьюринга, удвоив число её состояний, и изменим сдвиг головки считывания-записи так, чтобы в одной группе состояний работа машины была бы эквивалентна её работе в заштрихованной зоне, а в другой группе состояний машина работала бы так, как исходная машина работает в незаштрихованной зоне. Если при работе МТ встретится символ '*', значит головка считывания-записи достигла границы зоны:

Начальное состояние новой машины Тьюринга устанавливается в одной или другой зоне в зависимости от того, в какой части исходной ленты располагалась головка считывания-записи в исходной конфигурации. Очевидно, что слева от ограничивающих маркеров "*" лента в эквивалентной машине Тьюринга не используется.

Двумерные машины Тьюринга

Другие абстрактные исполнители и формальные системы вычислений

Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Глава 8. Введение в теорию машин Тьюринга // Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages, and Computation. - М.: Вильямс, 2002. - 528 с. - ISBN 0-201-44124-1.

Карпов Ю. Г. Теория автоматов. - Питер, 2003. - ISBN 5-318-00537-3.

Эббинхауз Г. Д., Якобс К., Ман Ф. К., Хермес Г. Машины Тьюринга и рекурсивные функции. - М.: Мир, 1972. - 262 с.

Нефёдов В. Н., Осипова В. А. Курс дискретной математики. - М.: МАИ, 1992. - 260 с.

# data[].attributes.attachment_link.title
Машина Тьюринга - Википедия

# data[].attributes.attachment_link.description
Маши́на Тью́ринга (сокр. МТ) - абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма. Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча - Тьюринга, способна имитировать всех исполнителей (с помощью задания правил перехода), каким-либо образом реализующих процесс пошагового вычисления, в котором каждый шаг вычисления достаточно элементарен.

# data[].attributes.headline
1940-ті роки: Робота над ЕНІАКом: 

# data[].attributes.subject
1940-ті роки: Робота над ЕНІАКом: 

# data[].attributes.body
У 1946 році ENIAC (Electronic Numerical Integrator and Computer) стає першим електронним цифровим комп'ютером загального призначення.

# data[].attributes.attachment_link.authors[].name
Лілія Медведенко

# data[].attributes.attachment_link.title
Історія розвитку ЕОМ (електронно обчислювальних машин). Перше покоління

# data[].attributes.body
UNIVAC I (акронім від англ. UNIVersal Automatic Computer I) — перший комерційний комп'ютер, створений в Сполучених Штатах, і третій комерційний комп'ютер у світі (після німецького Z4 і британського Ferranti Mark 1).

Переважно спроектований Джоном Екертом та Джоном Моклі, розробниками комп'ютера ENIAC. Проектні роботи почала їхня компанія Eckert-Mauchly Computer Corporation і завершила після того, як 1950 її купила Remington Rand, де Eckert-Mauchly Computer Corporation стала підрозділом UNIVAC, який виготовляв компʼютер UNIVAC I.

До початку випуску наступних моделей комп'ютер називався просто UNIVAC.

Перший екземпляр UNIVAC було встановлено в Бюро перепису населення США 31 березня 1951 року і запущено в дію 14 червня того ж року. П'ятий екземпляр (зібраний для Комісії з атомної енергії США) компанія CBS використала для прогнозування результатів виборів президента США 1952 року. За опитуванням 1 % населення, що мало право голосу, була коректно спрогнозована перемога Дуайта Ейзенхауера[1].

У 1950-і роки урядовим організаціям і фірмам було продано 46 машин UNIVAC І.

# data[].attributes.headline
1970-ті роки: Інтел випускає перший мікропроцесор Intel 4004 у 1971 році, що відкриває шлях до персональних комп'ютерів.

# data[].attributes.subject
1970-ті роки: Інтел випускає перший мікропроцесор Intel 4004 у 1971 році, що відкриває шлях до персональних комп'ютерів.

# data[].attributes.attachment_link.provider_name
Фонд Вікімедіа

# data[].attributes.attachment_link.authors[].name
Учасники проектів Вікімедіа

# data[].attributes.attachment_link.description
Intel 4004 — 4-бітовий мікропроцесор, випущений корпорацією Intel у 1971. 4004 — перший завершений центральний процесор, виконаний у вигляді однієї мікросхеми.

# data[].attributes.headline
1980-ті роки: Розквіт персональних комп'ютерів: 

# data[].attributes.subject
1980-ті роки: Розквіт персональних комп'ютерів: 

# data[].attributes.body
Поява IBM PC в 1981 році відкриває ринок особистих комп'ютерів для широкого кола споживачів.

# data[].attributes.attachment_link.readable_text
IBM PC 5150 з монохромним монітором 5151

IBM PC () - платформа персональних комп'ютерів, започаткована у серпні 1981 року фірмою IBM моделлю IBM 5150, загально відомою виключно як IBM PC.

Назва IBM PC протягом двох років була однозначною і відрізняла цей виріб від всіх інших тогочасних персональних комп'ютерів таких як ZX-81 або продукції серії Apple II. Коли у 1983 вийшла нова модель IBM PC/XT, фірма IBM скористалася популярністю назви IBM PC давши їй назву IBM PC/розширений (XT маркетингове скорочення англійського слова extended).

Популярність цією платформи та сумісних з нею виробів - близько 90 % світових комп'ютерів - привела до того, що для більшості споживачів персональний комп'ютер, ПІСІ ( англ. personal computer), ототожнюється з продукцією IBM PC.

Системна плата і шина

Системна плата оригінального IBM 5150 (IBM PC). Плата має п'ять слотів розширення (цей інтерфейс самою IBM у подальшому називався "PC/XT-bus", а іншими виробниками - "8-розрядна шина ISA"), і два роз'єми DIN для клавіатури і магнітофону.

На системній платі IBM PC розташовується центральний процесор Intel 8088, сокет для математичного співпроцесора Intel 8087, динамічна пам'ять, постійна пам'ять для BIOS, набір контролерів (DMA, IRQ, таймер, паралельний порт вводу-виводу) і мікросхем логіки, інтерфейси клавіатури, магнітофона (присутній лише у оригінальному IBM PC) і динаміка. Для під'єднання плат розширення присутні п'ять слотів системної шини ISA, з 8-розрядною шиною даних і 20-розрядною адреси.

Плата розширення Quadram Quadboard.

У слоти шини встановлюється відеокарта і контролер дискового накопичувача (дисковода чи жорсткого диска), а також (опційно) контролери інших інтерфейсів, наприклад, послідовного чи паралельного. Кожна карта розширення жорстко закріплюється гвинтом на корпусі комп'ютера, її роз'єми виходять на задню панель (не використані отвори у корпусі закриваються металевими заглушками, задля зменшення проникнення пилу всередину). Розширення пам'яті також здійснюється встановленням карт у слот ISA. Для цієї шини, що дуже швидко стала промисловим стандартом, сторонніми фірмами було розроблено велику кількість різноманітних контролерів вводу-виводу (наприклад, Ethernet, зв'язку з мейнфреймами і керуючими ЕОМ, та інші). П'яти слотів розширення у багатьох випадках було недостатньо, тому такі компанії, як Quadram and AST і інші випускали карти розширення, що об'єднували кілька контролерів та/або пам'ять на одній платі (Quadram QuadBoard, AST SixPak).

# data[].attributes.attachment_link.description
IBM PC () - платформа персональних комп'ютерів, започаткована у серпні 1981 року фірмою IBM моделлю IBM 5150, загально відомою виключно як IBM PC. Назва IBM PC протягом двох років була однозначною і відрізняла цей виріб від всіх інших тогочасних персональних комп'ютерів таких як ZX-81 або продукції серії Apple II.

# data[].attributes.body
Створення World Wide Web Тімом Бернерс-Лі в 1991 році сприяє революції в зв'язку та споживанні інформації через Інтернет.

# data[].attributes.attachment_link.authors[].name
Сніданок з 1+1

# data[].attributes.attachment_link.title
🖥️Історія інтернету: Як з’явився? Коли запустили? Та яким було найперше повідомлення?