Тепловая машина
<<  Синхронные машины Проект «паровая машина»  >>
Машина Поста
Машина Поста
Понятие «машины Поста»
Понятие «машины Поста»
Понятие «машины Поста»
Понятие «машины Поста»
Краткий обзор
Краткий обзор
Состав машины Поста
Состав машины Поста
Состав машины Поста
Состав машины Поста
Состав машины Поста
Состав машины Поста
Состав машины Поста
Состав машины Поста
Состав машины Поста
Состав машины Поста
Команды машины Поста
Команды машины Поста
Команды машины Поста
Команды машины Поста
Команды машины Поста
Команды машины Поста
Команды машины Поста
Команды машины Поста
Команды машины Поста
Команды машины Поста
Программа машины Поста
Программа машины Поста
Программа машины Поста
Программа машины Поста
Программа машины Поста
Программа машины Поста
Программа машины Поста
Программа машины Поста
Программа машины Поста
Программа машины Поста
Программа машины Поста
Программа машины Поста
Программа машины Поста
Программа машины Поста
Программа машины Поста
Программа машины Поста
Программа машины Поста
Программа машины Поста
Представление чисел
Представление чисел
Представление чисел
Представление чисел
Представление чисел
Представление чисел
Представление чисел
Представление чисел
Постулаты Поста
Постулаты Поста
Применение машины Поста
Применение машины Поста

Презентация: «Машина Поста». Автор: . Файл: «Машина Поста.ppt». Размер zip-архива: 2148 КБ.

Машина Поста

содержание презентации «Машина Поста.ppt»
СлайдТекст
1 Машина Поста

Машина Поста

Доклад по курсу «Системы Искусственного Интеллекта» Шариповой А.Ф. ИУ4-93

2 Понятие «машины Поста»

Понятие «машины Поста»

Машина Поста - это не реальная, а мысленная конструкция, которая существует лишь в нашем воображении

3 Понятие «машины Поста»

Понятие «машины Поста»

Состав машины Поста Команды машины Поста Программа машины Поста Представление чисел Постулаты Поста Применение машины Поста

4 Краткий обзор

Краткий обзор

Машина Поста (МП) — абстрактная вычислительная машина, которая отличается от машины Тьюринга большей простотой. Обе машины «эквивалентны» и были созданы для уточнения понятия «алгоритм».

5 Состав машины Поста

Состав машины Поста

6 Состав машины Поста

Состав машины Поста

Лента

Свойства ленты бесконечная и разделена на секции одинакового размера порядок, в котором расположены секции ленты, подобен порядку, в котором расположены все целые числа

7 Состав машины Поста

Состав машины Поста

Лента

В каждой секции ленты может быть: ничего не записано - секция пуста записана метка V - секция отмечена эта информация образует состояние ленты

8 Состав машины Поста

Состав машины Поста

Каретка

Каретка - считывающая и записывающая головка Свойства каретки: распознает стоит или нет метка в распознаваемой секции ставит или стирает метку в той секции, напротив которой она стоит

9 Состав машины Поста

Состав машины Поста

Работа

Суть работы: каретка передвигается вдоль ленты и печатает или стирает метки

10 Команды машины Поста

Команды машины Поста

Команды движения вправо Команды движения влево Команды печатания метки

11 Команды машины Поста

Команды машины Поста

Команды стирания метки Команды передачи управления Команды остановки

12 Команды машины Поста

Команды машины Поста

I – номер команды j – отсылка к команде j1 – отсылка к команде, если метка пуста j2 – отсылка к команде, если метка отмечена i, j, j1, j2 - натуральные числа

13 Команды машины Поста

Команды машины Поста

Примеры команд

14 Команды машины Поста

Команды машины Поста

Выводы

Чтобы Машина Поста начала работать, надо как-то расставить метки по секциям ленты и поставить каретку напротив секции с номером нуль.

15 Программа машины Поста

Программа машины Поста

Свойства программы: На первом месте – команда с номером 1 На k-м месте – команда с номером k Для каждой отсылки каждой команды списка найдется в списке такая команда, номер которой равен рассматриваемой отсылке

16 Программа машины Поста

Программа машины Поста

Пример программы:

17 Программа машины Поста

Программа машины Поста

Не верные программы: не выполняется первое свойство

18 Программа машины Поста

Программа машины Поста

Не верные программы: не выполняется второе свойство

19 Программа машины Поста

Программа машины Поста

Возможное завершение программы: 1. безрезультативная остановка (ошибка) – выполнение невозможной команды 2. результативная остановка – машина дошла до команды стоп 3. движение машины идет бесконечно

20 Программа машины Поста

Программа машины Поста

Возможное завершение программы:

Положение каретки до команды

Следующая команда

Завершение программы

Безрезультативная остановка

Результативная остановка

21 Программа машины Поста

Программа машины Поста

Пример

Начальное состояние ленты: Программа:

22 Программа машины Поста

Программа машины Поста

Команда

Положение каретки

Описание команды

Поставить метку

Перевести каретку на клетку вправо

Распознавание клетки. В клетке нет метки, значит следующей командой будет команда 4.

Перевести каретку на клетку вправо

23 Программа машины Поста

Программа машины Поста

Команда

Положение каретки

Описание команды

Распознавание клетки. В клетке есть метка, значит следующей командой будет команда 3.

Перевести каретку на клетку вправо

Стирание метки – невозможная команда

Безрезультативная остановка

Безрезультативная остановка

Безрезультативная остановка

24 Представление чисел

Представление чисел

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

25 Представление чисел

Представление чисел

Число n записывается на ленте массивом длины (n+1). Пример представления чисел 4, 0, 1:

26 Представление чисел

Представление чисел

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

27 Представление чисел

Представление чисел

28 Постулаты Поста

Постулаты Поста

1936 год статья «Финитные комбинаторные процессы – формулировка 1», «рабочая гипотеза»: 1. из разрешимости задачи, при помощи машины Поста, следует разрешимость при помощи алгоритма. 2. из разрешимости задачи, при помощи алгоритма, следует разрешимость при помощи машины Поста.

29 Применение машины Поста

Применение машины Поста

Для лучшего понимания термина «алгоритм» Для понимания принципов работы ЭВМ, в связи с наличием общих свойств: наличие атомарных носителей информации, наличие некоторого набора элементарных действий, работа на основе особой инструкции – программы.

«Машина Поста»
http://900igr.net/prezentacija/fizika/mashina-posta-189819.html
cсылка на страницу

Тепловая машина

11 презентаций о тепловой машине
Урок

Физика

134 темы
Слайды