Конечные машины и бесконечные машины. Понятие программы

Эффективная нумерация программы. Теорема о параметризации. Существование универсальной программы.

Машина – абстрактное устройство, осуществляющее переработку информации. Другие названия – «абстрактная машина», «автомат».

Конечная машина представляет собой набор из пяти объектов {A, S, Z, ν, ξ}, где

А={a₀, a₁,…, a_n} – конечный список символов (входной, внешний алфавит)

Z={z₀, z₁,…,z_m} – список выходящих символов (выходной алфавит)

S={s₀, s₁,…, s_z} – множество внутренних состояний

ν: S×A→S – функция перехода (в следующее состояние)

ξ: S×A→Z – функция выхода (Биркгоф, Бари – современная прикладная алгебра)

Примеры конечных автоматов. Покрытие и эквивалентность. Машина Тьюринга, как конечная машина.

Бесконечные машины определяются аналогично конечным. В определении бесконечных машин алфавиты A, Z или S могут быть бесконечным.

Типы бесконечных машин.

Теорема параметризации. Существование универсальной программы. Теорема об универсальности.

Компьютер фон Неймана

Архитектура Эккерта – фон Неймана и концепция хранимой программы. Историческая справка. Описание машины фон – Неймана.

Машина фон – Неймана представляет собой вычислительную систему, построенная на следующих принципах:

1. основными ее блоками является арифметико-логическое устройство, устройство управления, запоминающее устройство и устройство ввода-вывода.

2. Программы и данные хранятся в одной и той же памяти.

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

4. Внутренний код машины двоичен.

Подавляющее большинство вычислительных машин(компьютеров) в настоящее время является фон-неймановскими машинами. Свое название эта архитектура получила в честь американского ученого Джона фон Неймана (von Neumann). В литературе эта точка зрения воспринимается неоднозначно.

Архитектура машины фон – Неймана.

		Память