Содержание предисловие 2 веб-страницы 3 введение 6 1архитектура ЭВМ 17




НазваниеСодержание предисловие 2 веб-страницы 3 введение 6 1архитектура ЭВМ 17
страница73/78
Дата конвертации11.12.2012
Размер5.58 Mb.
ТипРеферат
1   ...   70   71   72   73   74   75   76   77   78

Машины Тьюринга


Вспомните, что для того, чтобы машина могла выполнить задачу, алгоритм выполнения этой задачи сначала необходимо найти нам. Следовательно, так как • для решения невычислимых функций алгоритмов не существует, такие функции находятся за пределами возможностей сегодняшних, да и завтрашних компьютеров. В попытке понять подобные ограничения машин многие исследователи создавали и изучали различные вычислительные устройства. Одно из них — машина Тьюринга, предложенная Аланом Тьюрингом в 1936 году, которая до сих пор используется в качестве инструмента для изучения возможностей алгоритмических процессов.

Основы машины Тьюринга


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



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

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

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

щую ячейку, которую будем называть текущей ячейкой. Алфавит в нашем примере состоит из символов 0, 1 и *. Лента машины может выглядеть следующим образом:

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

Истоки машины Тьюринга


Алан Тьюринг разработал концепцию машины Тьюринга в 1930-х годах, задолго до того, как технология развилась настолько, чтобы создать машины, известные нам сегодня. В действительности Тьюринг исходил из того, как люди производят вычисления при помощи карандаша и бумаги. Его целью была разработка модели, при помощи которой можно было бы изучать ограничения вычислительных процессов. Он приступил к работе вскоре после публикации в 1931 году знаменитой статьи Гёделя, раскрывающей пределы вычислительных систем, когда основные силы исследователей были направлены на изучение этих границ. В том же году, когда Тьюринг представил свою модель (1936), Эмиль Пост представил другую модель (ныне известную как система продукций Поста), которая должна была обладать теми же способностями, что и модель Тьюринга. Доказывая проницательность первых исследователей, их модели вычислительных систем до сих пор являются ценными инструментами в исследовании вычислительной техники.

У нашей машины есть состояния Начало, Прибавить, Перенос, Переполнение, Возврат и Останов. Действия, соответствующие каждому из этих состояний, и содержимое текущих ячеек перечислены в табл. 11.1. Мы предполагаем, что машина всегда начинает работу из состояния Начало.



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



Состояние машины = Прибавить

Для продолжения работы посмотрим в таблице, что следует делать в состоянии Прибавить с единицей в текущей ячейке. Таблица говорит нам заменить 1 в текущей ячейке на 0, передвинуть головку считывания-записи на одну ячейку влево и войти в состояние Перенос. Конфигурация машины:



Мы снова обращаемся к таблице за дальнейшими указаниями и обнаруживаем, что в состоянии Перенос, если в текущей ячейке содержится 0, необходимо заменить 0 на 1, переместить головку считывания-записи на одну ячейку вправо и войти в состояние Возврат.Конфигурация машины после этого:


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



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


Тезис Черча-Тьюринга


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

Предположение Тьюринга заключалось в том, что вычислимые по Тьюрингу функции являются вычислимыми функциями. Другими словами, он считал, что вычислительная мощь машин Тьюринга равна вычислительным способностям любой алгоритмической системы, или, что то же самое, что (в противоположность таким подходам, как таблицы или алгебраические формулы) концепция машины Тьюринга является средой, в которой можно выразить решения всех вычислимых функций. Сегодня это предположение называют тезисом Черча—Тьюринга (Church-Turing thesis), указывая на вклад, сделанный Аланом Тьюрингом и Алонзо Черчем. С момента появления первой работы Тьюринга было собрано множество подтверждений этого тезиса, и сегодня тезис Черча-Тьюринга является общепринятым. То есть считается, что вычислимые функции и функции, вычислимые по Тьюрингу, — это одно и то же.

Значение этого утверждения состоит в том, что оно дает нам способ проникнуть в суть возможностей и ограничений компьютеров. Точнее, оно определяет способности машин Тьюринга как стандарт, с которым можно сравнить возможности других вычислительных систем. Если вычислительная система способна выполнять все вычислимые по Тьюрингу функции, она считается настолько мощной, насколько вообще это возможно для любой вычислительной системы.
1   ...   70   71   72   73   74   75   76   77   78

Похожие:

Содержание предисловие 2 веб-страницы 3 введение 6 1архитектура ЭВМ 17 iconОсновы работы с Sharepoint в какое место веб-страницы разрешается вставить новую веб-часть (в браузере)?
В какое представление веб-страницы будут вноситься изменения, если выбрать команду Настроить эту страницу?
Содержание предисловие 2 веб-страницы 3 введение 6 1архитектура ЭВМ 17 iconВведение в физику и технологию элементной базы ЭВМ и компьютеров
Введение   8
Содержание предисловие 2 веб-страницы 3 введение 6 1архитектура ЭВМ 17 iconСодержание
Содержание размещают после титульного листа отчёта (как правило, на стр. 2). Слово «Содержание» рас­полагают посередине страницы...
Содержание предисловие 2 веб-страницы 3 введение 6 1архитектура ЭВМ 17 iconСоздание веб-страницы в простом текстовом редакторе
Давайте создадим  веб-страницу. Для этого нужно напечатать ее исходный код в простом текстовом редакторе  блокнот
Содержание предисловие 2 веб-страницы 3 введение 6 1архитектура ЭВМ 17 iconЗагрузка uploading теория
После того как набор html страниц веб-сайта создан. Все они связаны между собой с помощью ссылок. Страницы наполнены контентом. Таким...
Содержание предисловие 2 веб-страницы 3 введение 6 1архитектура ЭВМ 17 iconЛитература 153 Алфавитный указатель 155 Предисловие редактора русского издания Глубокоуважаемые коллеги! Содержа­ние этой книги значительно шире и глуб­же, нежели заявлено в ее названии. Я бы назвала ее «Лечение и реставрация молочных зубов»
Предисловие редактора русского издания 6 Введение 9 Предисловие 11 Благодарности 13
Содержание предисловие 2 веб-страницы 3 введение 6 1архитектура ЭВМ 17 icon        Информатика  Системы счисления и  арифметические основы эвм  
Введение   
Содержание предисловие 2 веб-страницы 3 введение 6 1архитектура ЭВМ 17 iconЯндекс - поисковая машина, способная по вашему запросу найти в русскоязычной части интернета наиболее подходящие веб-страницы, новости, картинки, статьи
Яндекс — поисковая машина, способная по вашему запросу найти в русскоязычной части интернета наиболее подходящие веб-страницы, новости,...
Содержание предисловие 2 веб-страницы 3 введение 6 1архитектура ЭВМ 17 iconВзаимодействие веб-сайтов по культуре с пользователем. 
Предисловие к русскому изданию   4 
Содержание предисловие 2 веб-страницы 3 введение 6 1архитектура ЭВМ 17 iconВзаимодействие веб-сайтов по культуре с пользователем. 
Предисловие к русскому изданию   4 
Разместите кнопку на своём сайте:
kak.znate.ru


База данных защищена авторским правом ©kak.znate.ru 2012
обратиться к администрации
KakZnate
Главная страница