Книги
чёрным по белому
Главное меню
Главная О нас Добавить материал Поиск по сайту Карта книг Карта сайта
Книги
Археология Архитектура Бизнес Биология Ветеринария Военная промышленность География Геология Гороскоп Дизайн Журналы Инженерия Информационные ресурсы Искусство История Компьютерная литература Криптология Кулинария Культура Лингвистика Математика Медицина Менеджмент Металлургия Минералогия Музыка Научная литература Нумизматика Образование Охота Педагогика Политика Промышленные производства Психология Путеводители Религия Рыбалка Садоводство Саморазвитие Семиотика Социология Спорт Столярное дело Строительство Техника Туризм Фантастика Физика Футурология Химия Художественная литература Экология Экономика Электроника Энергетика Этика Юриспруденция
Новые книги
Суворов С. "Танк Т-64. Первенец танков 2-го поколения " (Военная промышленность)

Фогль Б. "101 вопрос, который задала бы ваша кошка своему ветеринару если бы умела говорить" (Ветеринария)

Нестеров В.А. "Основы проэктирования ракет класса воздух- воздух и авиационных катапульных установок для них" (Военная промышленность)

Таранина И.В. "Гражданский процесс в схемах " (Юриспруденция)

Смоленский М.Б. "Адвокатская деятельность и адвокатура российской федерации" (Юриспруденция)
Реклама

Машина поста - Успенский В.А.

Успенский В.А. Машина поста — М.: Наука, 1988. — 96 c.
ISBN 5-02-013735-9
Скачать (прямая ссылка): mashinaposta1988.djvu
Предыдущая << 1 .. 24 25 26 27 28 29 < 30 > 31 32 33 34 35 36 .. 38 >> Следующая

устройство закладывается начальная информация, слагающаяся из частной
программы решения данной задачи и исходного данного, после чего работа (а
именно, переработка всего содержания запоминающего устройства)
8!
происходит по Универсальной Программе, воплощенной в конструкции машины
1).
Могут указать еще на одно, казалось бы, очень существенное отличие ЭВМ от
машины Поста: запоминающее устройство машины Поста - лента - имеет
бесконечную емкость, чего не может быть в реальных машинах. Однако и в
машине Поста можно заменить бесконечную ленту конечной лентой,
подклеиваемой по мере надобности (ведь все равно к каждому моменту работы
машины Поста будет использован только конечный кусок ленты): когда
каретка доходит до конца ленты, к нему подклеивается еще несколько
секций. С другой стороны, и внешнее запоминающее устройство ЭВМ может в
принципе неограниченно увеличивать свою емкость путем добавления новых
его частей (скажем, новых магнитных лент). Таким образом, и машину Поста
и ЭВМ можно трактовать как обладающие запоминающим устройством, конечным
в каждый данный момент, но неограниченно растущей емкости. Именно это
обстоятельство, делающее указанные машины пригодными для осуществления на
них любого алгоритма, главным образом и роднит машину Поста с ЭВМ и
позволяет рассматривать машину Поста как упрощенную модель ЭВМ.
]) Можно, впрочем, составить Универсальную Программу и для машины Поста,
а именно можно закодировать каждую программу машины Поста в виде постова
слова и помещать далее запись этой программы (т. е. запись
соответствующего слова) на ленте рядом с записью того исходного данного,
к которому она должна применяться. Можно, далее, составить программу -
Универсальную Программу, - которая, будучи применена к записи,
составленной из записи некоторой программы П и записи некоторого
исходного данного х, давала бы тот же результат, что и непосредственное
применение П к записи х. Однако в этом случае Универсальная Программа
будет всего лишь одной из возможных программ машины Поста: в случае же
ЭВМ Универсальная Программа вовсе не является одной из частных программ,
допустимых для ЭВМ, а реализована самой структурой ЭВМ.
ПРИЛОЖЕНИЕ I
В качестве приложения мы предлагаем перевод знаменитой статьи Эмиля Поста
"Финитные комбинаторные процессы, формулировка 1" (Emil L. Post "Finite
combinatory processes - formulation 1"). Статья эта была опубликована в
1936 г. в 3-м, сентябрьском номере 1-го тома "Журнала символической
логики ("The Journal of Symbolic Logic"), выходящего ежеквартально.
Публикация сопровождалась следующим примечанием редакции журнала:
"Получено 7 октября 1936 г. Читателю рекомендуется сравнить статью А. М.
Тьюринга "О вычислимых числах", долженствующую появиться вскоре в "Трудах
Лондонского математического общества". Настоящая статья, однако, хотя и
имеет более позднюю дату, написана совершенно независимо от статьи
Тьюринга". Статья Тьюринга (имеющая дату поступления 28 мая 1936 г.) была
опубликована в том же 1936 г. (Turing А. М. On computable numbers, with
an application to the Entscheidungsproblem//Proc. London Math. Soc., ser.
2. - 1936. - V. 42. - № 3-4, - P. 230-265. A corre-ction//Proc. London
Math. Soc., ser. 2.- 1937. - V. 43.- № 7. - P. 544-546). Итак,
ФИНИТНЫЕ КОМБИНАТОРНЫЕ ПРОЦЕССЫ*
ФОРМУЛИРОВКА 1
Эмиль JI. Пост
Предлагаемая формулировка может представить интерес при развитии
символической логики в направлении, намеченном теоремой Гёделя о
неполноте символических логик 1 и результатом Чёрча относительно
абсолютно неразрешимых проблем2.
1 G б d е 1 Kurt. Ober formal unentscheidbare Satze der Principia
Mathematica und verwandter Systeme I.//Monatsh. Math. Phys. - 1931. - Bd.
38. - H. 1. -S. 173-198. [Все подстрочные примечания к статье Э. Л. Поста
принадлежат ее автору. - Примеч. пер.]
2 Church. Alonzo. An unsolvable problem of elementary number
iheory//Amer. J. Math. - 1936, - V. 58. - Ns 2. - P. 345-363.
аз
Мы имеем в виду общую проблему, состоящую из множества конкретных
проблем. Решением общей проблемы будет такое решение, которое доставляет
ответ для каждой конкретной проблемы.
В излагаемой ниже формулировке того, что есть решение, используются два
понятия: пространство символов, в котором должна производиться работа,
приводящая от проблемы к ответу3, и зафиксированный неизменяемый набор
инструкций, который будет и управлять операциями в пространстве символов
и определять порядок, в котором эти инструкции должны применяться.
В нашей формулировке пространство символов состоит из бесконечной в обе
стороны последовательности мест, или ящиков; с точки зрения порядка,
таким образом, оно подобно ряду целых чисел ..., -3, -2, -1, О,
1, 2, 3, ... Решатель проблемы, или работник, может передвигаться и
работать в этом пространстве символов, будучи в состоянии в каждый
отдельный момент находиться и действовать лишь в одном ящике. Не считая
присутствия работника, каждый ящик может принимать лишь одно из двух
Предыдущая << 1 .. 24 25 26 27 28 29 < 30 > 31 32 33 34 35 36 .. 38 >> Следующая