Тезис Тьюринга-Черча об эквивалентности различных определений вычислимости.

До Тьюринга для определения формального алгоритма использовалось определение Черча. Определение основано на общей рекурсивности Геделя. В 36г. Тьюринг и Черч выдвинули тезис о том, что определения вычислимости могут быть сведены к определению Тьюринга. В частности любой алгоритм можно признать вычислимым, если он допускает реализацию на машине Тьюринга. Машина Тьюринга- гипотетическая: Выполняет считывание символа с ленты, передвинуть ленту, нанести символ на ленту. Рекурсивная программа вызывает сама себя.

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

1)ЦП - объединяющий в себе устройство управления и арифметико-логическое устройство.

2) ЗУ - запоминающее устройство - память.

3)УВВ - устройство ввода и вывода.

Программы и данные должны храниться в памяти. Ввод осуществляется через устройство ввода, аналогично вывод. Общее управление осуществляет Ц.П. Устройство ввода предназначено для общения с человеком и имеет механическую основу из-за этого их производительность меньше производительности ЦП, следовательно при управлении устройством ввода Ц.П. простаивает, поэтому есть связь между ЗУ и УВВ. Обмен данными - прямой доступ к памяти. Под программой понимают набор команд, извлекаемые в порядке их следования, либо в соответствии с управляющими командами. Данные хранятся в виде переменных, которые могут быть поименованы для последующей реализации и изменения. Программы данных хранятся в памяти. Память - последовательность ячеек для хранения порций информации. Доступ к информации ячеек осуществляется в соответствии с адресом (порядковым номером) информация хранится в двоичном виде.

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

Устройства ввода: Клавиатура (алф.цифр.), мышь, сканер, джойстик, микрофон.

Устройства вывода: Монитор, принтер, графопостроитель, звука.

Классификация памяти: постоянная и оперативная.

В процессоре объединены два устройства - управления - для считывания команд данных из памяти и общей координации команд и АЛУ - для простейших логических и арифметических операций.

Регистры специального назначения и регистры общего назначения.

РОН предназначены для общего назначения логических и арифметических операций. РСН - в их состав входят регистр - счетчик команд; регистр состояния программы; регистр указателя стека. Счетчик команд хранит адрес следующей команды; состояние программы - обязательно включает в себя флаги, характеризующие результат выполнения последней программы, флаг Z -, бит равный 1, если результат 0, и 0 если результат другой, флаг N - если результат отрицательный, флаг С 1 если был перенос из старшего разряда. Флаги используются для выполнения условных операций. Регистр стека - хранит адрес вершины стека. Стек - область памяти, доступ к которой осуществляется по принципу LIFO.

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

Существует группа операций.