lekcii5 (Лекции), страница 11

DJVU-файл lekcii5 (Лекции), страница 11 Информатика (116): Лекции - 1 семестрlekcii5 (Лекции) - DJVU, страница 11 (116) - СтудИзба2013-09-14СтудИзба

Описание файла

DJVU-файл из архива "Лекции", который расположен в категории "". Всё это находится в предмете "информатика" из 1 семестр, которые можно найти в файловом архиве МАИ. Не смотря на прямую связь этого архива с МАИ, его также можно найти и в других разделах. Архив можно найти в разделе "лекции и семинары", в предмете "информатика" в общих файлах.

Просмотр DJVU-файла онлайн

Распознанный текст из DJVU-файла, 11 - страница

Этому способствовали свойственные многим гениальным людям странности и чудачества в характере самого 'Гьюринга. Они же и привели к его трагической гибели от своеобразной английской рулетки: смешивая различные химические вещества он случайно получил яд и принял его Вовнутрь. 40 2.1.3 Нормальные алгоритмы Маркова асЫ 1 е.1 '1' = <ас]с] е.1> '0'; е.2 '0' = е.2 '1'; — '1' Ф >1 » 1> >Π— 0> > » < 1« — 0 0<ь 1 < ь-» 1 — »> 2.1.4 Тезис Тьюринга-таверна Использование алгоритмических моделей опирается на тезис Тьюринга-С1ерча о том, что всякий интуитивный алгоритм может быть выражен средствами одной из алгоритмических моделей. Опровергнуть этот тезис пока никому не удалось.

«Доказательством» же тезиса Тьюринга вполне может служить конструктивное построение фон Е!еймановской модели из '1'ьюринговской, предлагаемое в этом разделе курса. Существенно, что все алгоритмические модели описывают один и тот же класс процессов обработки сообщений. Доказано, что одни модели сводятся к другим, т. е, всякий алгоритм, описанный средствами одной модели, может быть описан и средствами другой. Наиболее близкой к вычислительным малпинам является алгоритмическая модель Тькь ринга. Поэтому именно эту модель мы выберем для формализации понятия алгоритма. ' Вы ъюжете больше узнать про личность академика А. А.

Маркова у профессора В. К. Титова, который выполнил диплоъшую работу па мехмате МГУ под его руководством. Алгоритмы Маркова предложены в 1950 г. нашим соотечественником академиком А. А. Марковым' (ълл.~ ]17, 251 На этой концепции основан оригинальный алгоритмический язык Рефал, предолженный в 1976 г. сотрудником Института Прикладной Математики В.

Ф. Турчиным, ныне профессором Ньюьйоркского университета. В. Ф. Турчин известен как составитель культовых сборников «Физики шутят» и «Физики продолжают шутить», в которых остроумие Турчина достигает таких же высот, как и его концептуальное кредо, изложенное в монографии [81~. Концелтпия НАМ и Рефала настолько ортогопальна тьюринговой и другим опсрационньлъл ъюделям, что она, непременно цитируется в научных статьях и упоминается во всех курсах информатики. В настоящее вреъля язык Рофал продолжает развиваться, в частности, в 2001 — 2003 гг, аспирант кафедры 806 М. А. Левинская, выполняя диссертационную работу на соискание учелюй степени кандида,та физико-ълатеълатических наук, предложила и успешно реализовала древовидное расширение Рефала ]981.

На леклцллл деълонст]зи1»устоя приъле]л но]зълальнлзго алгоритъла Ма])кона и эквивалс.нтная ему программа на Рефале прибавления 1 к десятичному числу (алгоритъл раоотает не с самим числОм, а с: Оуквами его цифрового изОО]за>кения 2.2 Машины Тьюринга 2.2.1 Неформальное описание Машина Тьюринга состоит из ограниченной с одного конца бесконечной ленты, разделенной на ячейки, и комбинированной читающей и пишущей головки, которая может перемещаться вдоль ленты от ячейки к ячейке. В каждой ячейке ленты может быть записан один знак алфавита А., называемого рабочим алфавитом МТ, либо пробел (его мы бучем обозначать знаком Л).

Головка МТ в каждый момент времени располагается над одной из ячеек ленты, называемой рабочей ячейкой, и воспринимает знак, записанный в этой ячейке (букву алфавита А или Л). При этом головка находится в одном из конечного множества (т!ть ттт,..., ц,) дискретных состояний, среди которых выделено одно начальное состояние тттт. В зависимости от состояния, в котором находится головка, и от буквы, записанной в рабочей ячейке, МТ выполняет одну из команд, составляя>щих ее программу. Выполнение команды состоит в выттолнепии элементарного действия, предписываемого этой командой, и переводе головки в новое состояние !которое, в частности, может совпадать со старым). Определено три вида элементарных действий: сдвиг головки на одну ячейку влево (если считать, что лента МТ ограничена слева, то для крайней левой ячейки сдвиг влево не определен), сдвиг головки на одну ячейку вправо, запись в рабочую ячейку какой-либо буквы рабочего алфавита А либо пробел (ттри этом буква, которая была записана в рабочей ячейке до выполнения записи, стирается).

Таким образом, каждая коьлаттда может сменить рабочуто ячейку, сделав новой рабочей ячейкой одну из соседних ячеек старой рабочей ячейки, или, не меняя рабочей ячейки, изменить знак, записанный в рабочей ячейке, и изменить состояние головки. Перед началом работы МТ па ее лепту записывается исходное сообщение так, что в каждуто ячейку летггы записывается одна буква сообщения, либо пробел. Ьудучи конечным, лк>бое сообщение занимает котточнос число ячеек ленты. При этом ячейки, расположенньи. справа, от последней буквы исходного стх>бтттения, заполняются пробелами и считаются тт!тстаьтмть В начале работы МТ ес головка приводится в начальное состояние тта и помещается над начальной рабочей ячейкой, которая определенным и фиксированным д тя каждой ковкретввоб ЛП' образом расположена относительно исходного сообщсния.

Обычно в качестве рабо тей ячейки мы будем брать ячейку, .расположенную вслед за исходным сообтттением, то есть, ячейку, содержащую символ пробела Л, расположенную непосредственно справа от пс>следней буквы сообщения (все ячейки, располо>кенньтт справа от начальной рабочей ячейки, содержат в начале работы МТ символы Л). Пара (т>ш а), где т>а — начальное состояние головки, и е алфавиту А 0 (Л) буква, записанная в начальной рабочей ячейке, определяет команду программы МТ, которая должна быть выполнена первой. В результате выполнения этой команды образуется новая пара (тт, а'), где тт -- текущее состояние головки, а' -- буква, записанная в текущей рабочей ячейке, которая определяет следуюшую команду и т.

д. Таким образом, работа МТ тю шостью определяется ее программой и сообщением, которое было записано па ленте ттеред началом работы МТ. Каждая команда МТ описывается упорядоченной четверкой символов (т!, .а, и, т!'), где ° д Е ~ -- символ текущего состояния головки; ° а Е А 0 (Л) буква, записанная в текущей рабочей ячейке: ° и Е (1., г) 0 А т.т (Л) символ выполняемого действия (и = 1 означает сдвиг головки влево, н = г сдвиг головки вправо, а и Е Ат т(Л) запись соответствующего знака в рабочую ячейку). ° д' Е ст силтвол состояния, в которое команда переводит головку. Пара (т/, а) определяет, какая из команд программы МТ должна быть выполнена (предполагается, что программа содержит не более одной команды, начинающейся с пары И,аИ 2.2.2 Математически строгое определение 00, , †,00 00, †,т,ОО 00,~,1,00 00,1,/,00 00,/, ,01 01, ,т,00 00, , †,п,00 00, †,т,п,00 ОО,т,1,п,00 00,1,/,п,00 00,/, ,т,ОО 1та программа сочетает кувырок палочки с ее продвижением вперед, фактически выполняя примитивную анимацию почттл по Диснею: инерция человеческого зрения домысливает эти рывки до тюлноценных кульбитов.

Поскольку начальное состояние совттадает с конечным, эта программа никогда не останавливается. В силу универсальности пятерок соответствующая МТ имеет вообще только одно состояние. Мы еще вернемся к этим программам после изучения теорем Шеннона, который показал ттезавершттлтость программ машин Тьюринга с одним состоянием. Хотя эти примеры иллюстрируют необходихлость дополнительных команд, а, следовательно, и состояний при программировании в четверках, все же можно составить аналогичный пример программы МТ в четверках с одним состоянием: 00, , †,00 00, , †,п,00 Определение 2.2.1.

Машиной Тьюринга называется упорядоченная четверка объектов Т = (А, ст, Р, ттт), где Т вЂ” символ МТ, А — конечное множество букв (рабочий алфавит), ят конечное множество символов (имен состояний), т/с имя начального состояния, Р - множество упорядоченных четверок (т/, а, и, ц'), т/, ц' Е ст, а б А0(Л), .и Е (т, г1стАО(Л) (программа), определяющее три функции: функцию выхода Рт. Я/ э А — А (А А т.т (Л)), функцию переходов Рч; Я * А — ф и функцию движения головки Г„: с„т э А — ~ (т, т, а) (символ в означает, что головка неподвижна).

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

Кроме того, сутцествуют и другие способы задания программ Тьктринга (диаграммы состояний, таблицы переходов). Рассмотрим рсализацинт одной и той же программы в четверках и пятерках. Программа 2.1. Пример бесконечной анимации ОО, †,Л,ОО ОО,Л,!,ОО оо,!,/,оо оо,/, ,оо 00, †, ),п,00 00, 1,),Н,ОО 00,1,/,Н,ОО 00,/, ,Н,ОО Но в этом примере пришлось пожертвовать движением и вместо кувыркающейся палочки мы получили вращающуюся на месте крутилку, используемую в ОС Н1Х11Х для текстовой индикации выполнения некоторого процесса. Определение 2.2.2.

Ситуацией (или состоянием ленты) называется упорядоченная пара объектов,5' = (=, й), где о' имя ситуации, ' сообщение, записанное на ленте, неотрицательное целое число, равное расстоянию (в ячейках) от края ленты до рабочей ячейки. Иными словами, Л' фиксирует положение рабочей ячейки на лепте. Иными словами, ситуация это Все "1ТО записано на лент1'. с Выдс.Ленной рабо'1ей я'к:Й- кой. Очень удобно следующее нагляднск обозначение для ситуации (линейная запись!): Я = 1111) и,, ., . и,„, (111„)а;„„... Н)„Л), где ( -- край ленты, а), Е А) ) (Л), ...

— пропущенные знаки, скобки () выделяют рабочую ячейку, ) бесконечш>1Й правый край ленты, образованный пустыми ячейками. Определение 2.2.3. Конфигурацией называется упорядоченная пара обт>ектов С = (о, г/), где .5' текущая ситуация, )1 текущее состояние головки. Для конфигурации будем использовать обозначение С = ~ана,,,...а,„,(У.,111,)а„„,...ОК,Л). Каждая конфигурация С однозначно определяет команду МТ, которая должна быть выполнена. После выполпеш)я указанной команды получается новая конфигурация С', про которую говорят, что она непосредственно следует за конфигурацией С: обозначение С =~ С', где ~ — символ бинарного отношения н1>посредственного следования. Отно)ПЕНИЕ Н11К)СРСДСТВ1)ННОГО СЛЕДОВВНИЯ ВЬ1ПОЛНЯ1>ТСЯ И ДЛЯ СИТУВЦИЙ > И О', СООТВЕТСТВУК)- щих конфигурациям С и С', сто мы будем обозначать 1) => .')'.

Свежие статьи
Популярно сейчас
Как Вы думаете, сколько людей до Вас делали точно такое же задание? 99% студентов выполняют точно такие же задания, как и их предшественники год назад. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
5288
Авторов
на СтудИзбе
417
Средний доход
с одного платного файла
Обучение Подробнее