Компьютерная Лаборатория

  1. Что такое машина Тьюринга? Машина Тьюринга - это гипотетическая машина, о которой математик Алан...
  2. Простая программа
  3. Состояние машины
  4. Конечные автоматы

Что такое машина Тьюринга?

Машина Тьюринга - это гипотетическая машина, о которой математик Алан Тьюринг придумал в 1936 году. Несмотря на свою простоту, машина может имитировать ЛЮБОЙ компьютерный алгоритм, каким бы сложным он ни был!

Несмотря на свою простоту, машина может имитировать ЛЮБОЙ компьютерный алгоритм, каким бы сложным он ни был

Выше очень простое представление машины Тьюринга. Он состоит из бесконечно длинной ленты, которая действует как память в типичном компьютере или в любой другой форме хранения данных. Квадраты на ленте обычно пустые в начале и могут быть написаны с символами. В этом случае машина может обрабатывать только символы 0 и 1 и «» (пусто) и, таким образом, называется машиной Тьюринга с 3 символами.

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

  1. Прочитайте символ на квадрате под головой.
  2. Отредактируйте символ, написав новый символ или удалив его.
  3. Переместите ленту слева направо на один квадрат, чтобы машина могла читать и редактировать символ на соседнем квадрате.

Простая демонстрация

В качестве тривиального примера, демонстрирующего эти операции, давайте попробуем напечатать символы «1 1 0» на изначально чистой ленте:

В качестве тривиального примера, демонстрирующего эти операции, давайте попробуем напечатать символы «1 1 0» на изначально чистой ленте:

Сначала мы пишем 1 на квадрате под головой:

Сначала мы пишем 1 на квадрате под головой:

Далее мы перемещаем ленту влево на одну клетку:

Далее мы перемещаем ленту влево на одну клетку:

Теперь напишите 1 на новом квадрате под заголовком:

Теперь напишите 1 на новом квадрате под заголовком:

Затем мы снова перемещаем ленту влево на одну клетку:

Затем мы снова перемещаем ленту влево на одну клетку:

Наконец, напишите 0 и все!

Наконец, напишите 0 и все

Простая программа

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

Символ чтения Инструкция записи Инструкция перемещения Пусто Нет Нет 0 Запись 1 Переместить ленту вправо 1 Запись 0 Переместить ленту вправо

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

Давайте посмотрим, что эта программа делает с нашей лентой из предыдущего конечного пункта инструкций:

Текущий символ под заголовком - 0, поэтому мы пишем 1 и перемещаем ленту вправо на один квадрат.

Текущий символ под заголовком - 0, поэтому мы пишем 1 и перемещаем ленту вправо на один квадрат

Читаемый символ теперь равен 1, поэтому мы пишем 0 и перемещаем ленту вправо на один квадрат:

Читаемый символ теперь равен 1, поэтому мы пишем 0 и перемещаем ленту вправо на один квадрат:

Аналогично, символ чтения равен 1, поэтому мы повторяем одни и те же инструкции.

Аналогично, символ чтения равен 1, поэтому мы повторяем одни и те же инструкции

Наконец, «пустой» символ читается, поэтому машина ничего не делает, кроме непрерывного чтения пустого символа, поскольку мы дали ему команду повторить последовательность чтения-записи-перемещения без остановки.

На самом деле программа неполная. Как машина повторяет последовательность бесконечно, и как машина прекращает запуск программы? Программа рассказывает это с концепцией состояния машины .

Состояние машины

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

Состояние

Символ чтения Инструкция записи Инструкция перемещения Следующее состояние Состояние 0 Пусто Нет Нет Состояние останова 0 Запись 1 Перемещение ленты в правильное состояние 0 1 Запись 0 Перемещение ленты в правильное состояние 0

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

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

Конечные автоматы

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

Состояние Символ чтения Инструкция записи Инструкция перемещения Следующее состояние Состояние 0 Пусто Запись пусто Переместите ленту влево Состояние 1 0 Запись 1 Переместите ленту вправо Состояние 1 1 Запись 0 Переместите ленту вправо Состояние 0 Состояние 1 Пусто Написать пусто Переместить лента вправо Стоп-состояние 0 Запись 1 Перемещение ленты в левое состояние 1 1 Запись 0 Перемещение ленты в левое состояние 1

Для инструкции записи «None» было изменено на «Write blank» для единообразия (так что упоминаются только символы машины), и следует отметить, что они эквивалентны.

Вместо таблицы состояний программа также может быть представлена ​​диаграммой состояний:

Из того места, где программа находилась ранее, вместо того, чтобы ничего не делать и останавливаться после того, как машина обнаруживает пустой символ, мы даем команду переместить ленту влево, прежде чем перейти в состояние 1, где происходит обратное преобразование битов.

Из того места, где программа находилась ранее, вместо того, чтобы ничего не делать и останавливаться после того, как машина обнаруживает пустой символ, мы даем команду переместить ленту влево, прежде чем перейти в состояние 1, где происходит обратное преобразование битов

Затем мы снова инвертируем биты, на этот раз перемещая ленту влево, а не вправо.

Затем мы снова инвертируем биты, на этот раз перемещая ленту влево, а не вправо

Наконец, читается пустой символ, поэтому мы перемещаем ленту вправо, чтобы вернуться к тому, с чего начали, и останавливаем программу.

Наконец, читается пустой символ, поэтому мы перемещаем ленту вправо, чтобы вернуться к тому, с чего начали, и останавливаем программу

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

В второй раздел Давайте узнаем о светодиодах, выводах GPIO, резисторах и питоне, прежде чем приступить к созданию нашей машины Тьюринга!

Похожие

Что такое хост-адаптер?
Обновлено: 26.04.2017 от Computer Hope Хост-адаптер , HBA ( хост-адаптер шины ) или хост-контроллер - это часть компьютера, которая обеспечивает связь с такими устройствами, как жесткие диски , Ethernet , волокно,
Продажа в Allegro - что такое правовое регулирование? - eKomercyjnie.pl: eKomercyjnie.pl
Наверное, каждый, кто регулярно пользуется почтовым ящиком, ценит ценную информацию и не любит ходить
Freewrite или машина, на которой можно ... написать
Я долго думал, для кого это оборудование. И я пришел к одному выводу - конечно, не на 99,9 процента. читатели, которые начинают читать этот текст. А как насчет оставшихся 0,01 процента? Ну ... наверное не для них, хотя им бы это понравилось. Не стесняйтесь просматривать пишущую машинку Freewrite - возможно, самый странный гаджет, который я когда-либо тестировал в сети Spider. Начнем
USB, Firewire & Thunderbolt: что лучше для аудио?
Если вы выбираете новый аудиоинтерфейс или новый компьютер, каковы плюсы и минусы множества предлагаемых протоколов подключения? Лучше купить аудиоинтерфейс, который подключается к моему компьютеру через USB, Firewire, Thunderbolt или PCIe? Какой из них еще пригодится через пять или 10 лет? И почему вокруг нет больше интерфейсов USB 3? По мере того, как расширяются наши возможности получения данных от A до B - недавно были добавлены USB 3, Thunderbolt и Thunderbolt 2, в то время как
Не знаете, что такое подарок Санты? Что купить у родственников? У многих людей (в том числе и у меня) есть пробл...
Не знаете, что такое подарок Санты? Что купить у родственников? У многих людей (в том числе и у меня) есть проблема с подарками для своих близких. Независимо от того, будет ли это день рождения, именины, юбилей или Дед Мороз, проблема всегда одна и та же - какой подарок купить? Я выберу то, что я выберу? От случая к случаю, от Рождества до Рождества, от одного пропущенного подарка к другому, я всегда обещаю себе, что в следующий раз, когда я покрою это раньше, я спрошу и т. Д. ...
Новый покемон для смартфонов. Pokemon Quest для Android и iPhone
Последняя игра с милыми существами в главной роли впервые дебютировала на консоли Nintendo Switch, но согласно анонсу Pokemon Quest приземлилась именно на смартфонах. Игру можно скачать из App Store и Google Play. Во время конференции, прямо перед выставкой E3, не было анонсировано ни одной, ни трех игр из серии Pokemon. Помимо первой RPG-игры на Nintendo Switch (Pokemon Let's GO в вариантах Pikachu и Eevee) и первой полноценной игры из основной серии,
Регистрация бизнеса - что нужно знать в начале? - деньги это женщина
Я работаю фрилансером в течение некоторого времени. Однако несколько недель назад я стал официальным владельцем бизнеса. Какова регистрация хозяйственной деятельности? Собираетесь ли вы идти своим путем? Посмотрите, что вам нужно знать в начале.
Сеть Tor
Владельцы сайтов, обеспокоенные безопасностью и конфиденциальностью, часто задают вопросы о Tor, сети анонимности и таких приложениях, как веб-браузер Tor, которые используют сеть Tor. Мы собрали список часто задаваемых вопросов по Tor, чтобы попытаться ответить на некоторые из наиболее распространенных вопросов, которые возникают у администраторов сайта по поводу Tor. Что такое Tor? Название Tor происходит от «Лукового маршрутизатора», который был первым именем проекта, когда
IPad Pro - это отличная возможность стать настоящей заменой ПК
CNET / CBSi Если iPad Pro станет настоящей заменой ПК, Apple должна предоставить пользователям более широкий доступ к их собственным данным. Я понимаю, почему iOS изначально не поставлялась с файловым менеджером по типу Finder в OS X или Windows Explorer в Windows. Apple хотела, чтобы iOS была простой альтернативой ПК и Mac, и одним из способов достижения этой цели было блокирование
Все, что вам нужно знать при поездке в Италию
Вот мой первый (и, вероятно, единственный) оригинальный путеводитель, который творит чудеса ! И как? Очень просто. Спасает жизни, защищает ваши кошельки, гладит вас по вкусу, заботится о ваших международных отношениях и (самое главное) сохранит ваше чувство юмора во всем этом. Ничего, просто тренируйся! Причиной этого текста стала статья, найденная в сети, в которой я узнал, что
Что такое карта сайта?
Если вы когда-либо работали с цифровым агентством или участвовали в процессе веб-дизайна, вы наверняка слышали термин «карта сайта». Похож на географическую карту это помогает людям находить места, которые они ищут в реальном мире, и карта сайта - это файл, в котором вы можете перечислить веб-страницы своего сайта, чтобы сообщить Google и другим поисковым системам об организации содержания вашего сайта. Карта сайта также

Комментарии

Если вы не курите, то вам придется притворяться, что никто никогда не трахался со всеми плохими девочками, потому что он охранял сумки с батареями в зоне отдыха, верно?
Если вы не курите, то вам придется притворяться, что никто никогда не трахался со всеми плохими девочками, потому что он охранял сумки с батареями в зоне отдыха, верно? Тем не менее, выкуривание сигарет у девушек - не такой хороший способ начать разговор, как грустный, но настоящий - зажигалка. Вы помните, как кто-то в школе однажды сказал, что зажигать сигарету для девочки - это все равно, что заниматься с ней третьим сексом? Ну, он был прав. Если эта метафорическая треть - та часть,
Или это похоже на то, что это было быстро собрано одним человеком?
Или это похоже на то, что это было быстро собрано одним человеком? Информация о компании - принадлежит ли сайт компании с названием компании в нижнем колонтитуле? Условия использования и политика конфиденциальности - есть ли у них условия обслуживания и политика конфиденциальности? Контактная информация - предоставляют ли они физический контактный адрес на странице контактов или в своих условиях обслуживания? Поиск домена - Google доменное имя в кавычках,
Что такое Xiaomi Mi 8 Pro?
Что такое Xiaomi Mi 8 Pro? Китайский технический гигант Xiaomi наконец-то готова продвинуться на рынок Великобритании , делая заявление с его устройством запуска, Mi 8 Pro (произносится «я»). Фактически, компания вывела на британские берега залп оборудования вместе с рядом смартфонов. Британские любители технологий могут также рассчитывать получить в свое распоряжение скутер Mi Electric, фитнес-трекер
Что это?
Что это? Может ли Nokia рассчитывать на то, что ее последний ребенок восстановит свою репутацию серьезного производителя и сможет соблазнить самых требовательных? Ответьте на этом испытательном стенде. Взгляд, который имеет характер Lumia 800 берет на себя дизайн N9 (под MeeGo) и доступен в черном (мат!), Голубом и пурпурном. Его внешний вид, особенно удачный благодаря своей цельной поликарбонатной оболочке, трезв и утончен.
Не знаете, что такое подарок Санты?
Не знаете, что такое подарок Санты? Что купить у родственников? У многих людей (в том числе и у меня) есть проблема с подарками для своих близких. Независимо от того, будет ли это день рождения, именины, юбилей или Дед Мороз, проблема всегда одна и та же - какой подарок купить? Я выберу то, что я выберу? От случая к случаю, от Рождества до Рождества, от одного пропущенного подарка к другому, я всегда обещаю себе, что в следующий раз, когда я покрою это раньше, я спрошу и т. Д. ... к сожалению,
Новые обычно имеют больше дополнений, но означает ли это, что они будут лучше, чем их предшественники?
Новые обычно имеют больше дополнений, но означает ли это, что они будут лучше, чем их предшественники? Что если данная модель отличается только несколькими функциями, которые мы не рассматривали ранее? Нам действительно нужно 15 приложений и доступ в интернет когда мы ищем приемник только для просмотра ТВ и фильмов? Зачем переплачивать?
Что именно означает это число?
Что именно означает это число? С точки зрения SEO, в немецком Hetzner мы можем получить 2228 различных классов C-адресов, тогда как в этом префиксе трансляции будет ровно 512. Hetzner публикует 16 префиксов, которые дают общее количество 570368 IP-адресов, которые будут использоваться. Номер AS также важен. В начале его определения он был записан в двухбайтовом формате, что означает, что максимально возможное количество AS может быть 65536. К счастью, способ записи в четырехбайтовые и AS много
Все, что вам нужно сделать, это купить один за 1,5?
Все, что вам нужно сделать, это купить один за 1,5? И в течение 100 минут вы можете путешествовать один раз на метро и любое количество раз на автобусе и трамвае. Внимание! Билет на целый день (6?) Действителен только до полуночи, а не 24 часа, как требует логика. Штрафы за отсутствие билета, к сожалению, чистят кошельки до нуля (а то и больше), доходя до 500? , 5. Кофе за столом. В баре без туалета. Прежде всего, если вы хотите почувствовать
Означает ли это, что мы завершаем транзакцию за пределами eBay?
Означает ли это, что мы завершаем транзакцию за пределами eBay? Нет, вы не завершаете транзакцию за пределами eBay, когда делаете лучшее предложение. Сделки по наилучшему предложению согласовываются по каналам eBay и совершаются на eBay. Прочитайте нашу полную политику Предложения о покупке или продаже вне обзора политики eBay Мы не разрешаем нашим членам использовать eBay для связи друг с другом, чтобы делать предложения о покупке или продаже товаров
Так что, если у нас есть место для нее, именно она стала королевой нашей ванной - почему бы не сделать это?
Так что, если у нас есть место для нее, именно она стала королевой нашей ванной - почему бы не сделать это? Прямоугольная ванна Отлично Призма Это модель ванны, которая является одной из наиболее часто покупаемых в нашем магазине. Это связано с несколькими факторами. Прежде всего, эти ванны можно приобрести различной длины. Таким образом, они впишутся в маленькие и большие ванные комнаты. Эти ванны были сделаны из акрила. Этот материал имеет ряд
Может быть, это не Nikon, но это, безусловно, хорошая вспышка, она отлично справляется со своей работой, и действительно, я упомянул цену в 81 доллар?
Может быть, это не Nikon, но это, безусловно, хорошая вспышка, она отлично справляется со своей работой, и действительно, я упомянул цену в 81 доллар? Незначительные вещи могут быть прощены из-за высокой мощности и хороших характеристик и невероятной цены. Может быть, одно слабое место. Эта фотография - моя (старая) батарейная дверь. На каждой стороне есть три одинаковых фиксирующих выступа, которые удерживают дверь закрытой. Два проушины (по обе стороны двери) со временем сломались

Что такое машина Тьюринга?
Как машина повторяет последовательность бесконечно, и как машина прекращает запуск программы?
А как насчет оставшихся 0,01 процента?
Если вы выбираете новый аудиоинтерфейс или новый компьютер, каковы плюсы и минусы множества предлагаемых протоколов подключения?
Лучше купить аудиоинтерфейс, который подключается к моему компьютеру через USB, Firewire, Thunderbolt или PCIe?
Какой из них еще пригодится через пять или 10 лет?
И почему вокруг нет больше интерфейсов USB 3?
Что купить у родственников?
Не знаете, что такое подарок Санты?
Что купить у родственников?