Цель: Формирование умений и навыков по разработке программ машин Тьюринга.
1. изучить устройство машины Тьюринга
2. научиться читать и выполнять программы, написанные для машины Тьюринга
3. научиться разрабатывать программы для машины Тьюринга.
· Техническое: ПК, сканер, принтер, интерактивная доска
· Методическое: инструкционная карта, задание для самостоятельного выполнения
· Программное: Windows XP, тренажер «Машина Тьюринга».
Теоретические сведения: Программы для машин Тьюринга записываются в виде таблицы, где первые столбец и строка содержат буквы внешнего алфавита и возможные внутренние состояния автомата (внутренний алфавит). Содержимое таблицы представляет собой команды для машины Тьюринга.
Буква, которую считывает головка в ячейке (над которой она находится в данный момент), и внутренне состояние головки определяют, какую команду нужно выполнить. Команда определяется пересечением символов внешнего и внутреннего алфавитов в таблице.
Как запрограммировать на машине Тьюринга сложение? Душкин объяснит
Чтобы задать конкретную машину Тьюринга, требуется описать для нее следующие составляющие:
1. Внешний алфавит. Конечное множество (обозначают буквой А), элементы которого называются буквами (символами). Одна из букв этого алфавита (например, а0) должна представлять собой пустой символ. Например, алфавит машины Тьюринга, работающей с двоичными числами, задается в виде A = . Непрерывную цепочку символов на ленте называют словом.
Автоматом называют устройство, работающее без участия человека. Автомат в машине Тьюринга имеет несколько состояний и при определенных условиях переходит из одного состояния в другое. Множество состояний автомата называют внутренним алфавитом.
3. Внутренний алфавит. Конечное множество состояний каретки (автомата). Обозначается буквой Q=. Одно из состояний — q1- должно быть начальным (запускающим программу).
Еще одно из состояний (q0) должно быть конечным (завершающим программу) – состояние остановка.
Таблица переходов. Описание поведения автомата (каретки) в зависимости от состояния и считанного символа.
Автомат машины Тьюринга в процессе своей работы управляется программой, во время каждого шага которой выполняются последовательно следующие действия:
· Записывать символ внешнего алфавита в ячейку (в том числе и пустой), заменяя находившийся в ней (в том числе и пустой).
· Передвигаться на одну ячейку влево или вправо.
· Менять свое внутреннее состояние.
Поэтому при составлении программы для каждой пары (символ, состояние) нужно определить три параметра: символ ai из выбранного алфавита A, направление перемещения каретки («←” — влево, «→” — вправо, «точка” — нет перемещения) и новое состояние автомата qk. Например, команда 1 «←” q2 обозначает «заменить символ на 1, переместить каретку влево на одну ячейку и перейти в состояние q2”.
1. В рабочей тетрадке запишите тему, цель и задачи работы.
2. Приступите к выполнению упражнений.
Функции, вычисляемые по Тьюрингу
3. Выполните задание.
4. Сделайте вывод по работе.
Упражнение 1 На ленте записано число в двоичной системе счисления. Каретка находится где-то над числом. Требуется увеличить число на единицу.
Чтобы решить задачу, нам нужно:
· определить алфавит машины Тьюринга А,
· определить набор состояний Q,
· составить программу (т.е. для каждой пары (аi,qi) определить команду автомата.)
Алфавит машины Тьюринга, работающей с двоичными цифрами будет включать цифры 0, 1 и пробел a0. Т.е. А=.
Определим возможные состояния:
1. q1 — автомат ищет правый конец слова (числа) на ленте
2. q2 — автомат увеличивает число на 1, проходя его слева направо и останавливается, закончив работу.
1 часть. q1 — автомат ищет правый конец слова (числа на ленте)
1)если в рабочей ячейке записано 0 — переместиться вправо
2)если в рабочей ячейке записано 1 — переместиться вправо
3) если в рабочей ячейке пробел, переместить каретку влево и перейти в состояние q2
Составим таблицу переходов для q1 т.о.:
| q1 | |
| 0 → q1 | |
| 1 → q1 | |
| a0 | a0 ← q2 |
2 часть. q2 — автомат увеличивает число на 1, проходя его слева направо и останавливается, закончив работу.
1) если в рабочей ячейке записана цифра 0, записать в нее 1 и стоп
2) если в рабочей ячейке записана цифра 1, выполнить перенос в старший разряд — записать в ячейку 0 и переместиться влево.
3) если в рабочей ячейке пробел, записать в нее 1 и стоп.
Добавим в нашу таблицу состояние q2:
| алфсостояния | q1 | q2 |
| 0 → q1 | 1. q0 | |
| 1 → q1 | 0 ← | |
| a0 | a0 ← q2 | 1. q0 |
Построенная таблица и есть программа для машины Тьюринга.
Упражнение 2. Допустим, на ленте есть слово, состоящее из символов #, $, 1 и 0. Требуется заменить все символы # и $ на нули. В момент запуска головка находится над первой буквой слова слева. Завершается программа тогда, когда головка оказывается над пустым символом после самой правой буквы слова.
Примечание: длина слова и последовательность символов значения не имеют. На рисунке приводится пример последовательности выполнения команд для конкретного случая.
Если на ленте будет другое слово, то и последовательность выполнения команд будет другой. Несмотря на это, данная программа для машины Тьюринга (на рисунке – таблица слева) применима к любым словам описанного внешнего алфавита (соблюдается свойство применимости алгоритма ко всем однотипным задачам – массовость).
Задания для самостоятельного выполнения
1. Построить таблицу машины Тьюринга, которая заменяет все единицы на нули, а все нули на единицы. Пример. Исходное число 111001. Результат – 000110.
2. Построить таблицу машины Тьюринга, которая удаляет из числа все нули, например, число 1001110 преобразует к виду 1111. Эта задача уже сложнее и требует ввести в рассмотрение более двух состояний.
3. Построить машину, имеющую два конечных состояния, условно обозначаемых как YES и NO. Машина должна завершить работу в состоянии YES, если число единиц в записи числа нечетное, и в состоянии NO– в противном случае.
4. Построить машину, имеющую два конечных состояния, условно обозначаемых как YES и NO. Машина должна завершить работу в состоянии YES, если в записи числа имеется три подряд идущих единицы, и в состоянии NO– в противном случае.
5. Построить машину Тьюринга, которая получает обратный порядок записи числа, например, исходное число 111001, результат 100111.
6. Построить машину Тьюринга, которая меняет местами соседние два элемента попарно. Пример. Исходное число 011001 заменяется на 100110.
Источник: cyberpedia.su
Научный форум dxdy
Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе «Помогите решить/разобраться (М)».
Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.
Не ищите на этом форуме халяву , правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.
Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.
Машина Тьюринга для заданной функции
Машина Тьюринга для заданной функции
05.05.2009, 09:08
Построить машину Тьюринга Поста, вычисляющую функцию f, и проиллюстрировать ее работу на примере слова А.
f(x,y,z)=max, A=1*111*111.
Это пара чисел m,n 
Программа
складывает числа, а как найти max?
05.05.2009, 09:41
NatNiM в сообщении #211070 писал(а):
а как найти max?
бегать влево-вправо, слева отделятьть по одной единичке на шаг влево, справа отделять по одной единичке на шаг вправо.
Которое из чисел раньше кончится, то будет min.
А второе — max.
05.05.2009, 09:44
Xaositect писал(а):
NatNiM в сообщении #211070 писал(а):
а как найти max?
бегать влево-вправо, слева отделятьть по одной единичке на шаг влево, справа отделять по одной единичке на шаг вправо.
Которое из чисел раньше кончится, то будет min.
А второе — max.
Так это получится, как я понимаю, 2 отдельные программы: одна вначале складывает, затем вторая определяет max?
05.05.2009, 09:47
ну можно сначала сложить и перейти в какое-нибудь ранее не использованное состояние, и начать вторую программу писать с неиспользованными состояниями. Получится одна большая программа.
05.05.2009, 12:45
Xaositect писал(а):
ну можно сначала сложить и перейти в какое-нибудь ранее не использованное состояние, и начать вторую программу писать с неиспользованными состояниями. Получится одна большая программа.
А на вход, стало быть, подавать все три числа? Как же можно одновременно их так обработать!
05.05.2009, 13:14
Давайте я напишу какой-нибудь пример.
Вот допустим.
Даны 3 числа, их все надо сложить.
Пишем сначала программу, которая складывает первые два. Только чуть-чуть отличающуюся от той, что Вы написали.
Она переводит конфигурацию
в конфигурацию 
, не затрагивая того, что стоит правее . Теперь, если мы заменим
на 
и напишем эту программу еще раз, только с 
вместо 
, то получим программу, которая сначала переводит 
в 
, а потом 
Машины Тьюринга можно так склеивать.
05.05.2009, 13:36
Xaositect писал(а):
Давайте я напишу какой-нибудь пример.
Вот допустим.
Даны 3 числа, их все надо сложить.
Пишем сначала программу, которая складывает первые два. Только чуть-чуть отличающуюся от той, что Вы написали.
Она переводит конфигурацию в конфигурацию , не затрагивая того, что стоит правее .
Теперь, если мы заменим на и напишем эту программу еще раз, только с вместо , то получим программу, которая сначала переводит
в , а потом
Машины Тьюринга можно так склеивать.
ну так последнее выражение — сумма трех чисел, а не max. Или отсюда можно плясать к max?
Источник: dxdy.ru
Составить программу для машины Тьюринга, вычисляющую значения функции O^n(X1. Xn)
В университете задали задание, но я не понимаю, что здесь конкретно нужно вычислять, потому что внутри функции никаких действий не выполняется.
Unreplied Threads
Comparing power readings for the same supply through an inverter’s software, and through a Shelly Energy Meter
- RenegadeAndy
- 8 minutes ago
- Physics
- Replies: 0
I have an inverter for a solar system, which at a given point of time shows me that we are exporting 768W to the grid.
Through a ShellyEM and via home assistant, (using a different CT Clamp) I can see the following:
Clearly this power value of -949.4W doesn’t tie up to the inverter’s measurement of the exported power.
I decided to consider what the power factor measurement of -0.79 means.
Guessing my way through this, if I do (949.4/100) * 79 we get a value of -750W — which is relatively close to the value I see on my inverter’s software. Is that pot luck? Or is this correct logic — and probably what the inverter itself is doing?
Am I correct in using the power factor to correct the power measurement the ShellyEM reports?
How to select a buffer IC for HCPL3120 optocoupler based gate drive circuit?
- ankit kumar
- 8 minutes ago
- Physics
- Replies: 0
I am new to this forum. I am trying to design a MOSFET gate driver board of my own and I am thinking of using HCPL-3120 as the optocoupler with a VCC of +15 Volts and VEE of -8 Volts. I am using TMS320F28335 as the DSP controller. After referring the datasheet of HCPL-3120 (figure 25 in particular) I am unable to find a suitable open-collector/open-drain buffer IC to put in between the optocoupler and the DSP kit. I have 3 questions about this buffer IC.
Q1) Can you suggest a suitable 5 pin buffer IC for my design? Rather, how do I select a buffer IC for myself?
Q2) Can I give a floating input to my buffer? I mean, can I connect only the PWM output directly to my buffer without any ground?
Q3) I will generate an isolated 5 V supply using a 12 V transformer. Should the 2 grounds shown on the left of the optocoupler in the attached image be connected to the ground of my isolated 5 V supply?
Источник: s2.solveforum.com