Разработка сайта для Вашего бизнеса. Веб дизайн. Дизайн логотипа, фирменного стиля, рекламная фотография . Комплексный рекламный креатив.

Ralex. We do the work.
На рынке с 1999го года. Средняя ценовая категория. Ориентация на эффективность решений.
Ознакомтесь с нашим портфолио
Узнайте больше о услугах
Свяжитесь с нами:
E-mail: [email protected]
Tel: (044) 587 - 84 - 78
Custom web design & дизайн и разработка сайта "под ключ"
Креативный, эффективный дизайн. Система управления сайтом (СУС).
Custom flexible разработка систем электронной коммерции
Система e-commerce разрабатывается под индивидуальные потребности. Гибкая функциональность.
Search Engine Optimzation & оптимизация под поисковые системы (SEO)
Постоянная оптимизация и мониторинг сайта в поисковых системах. Достигаем результата быстро и эффективно
Custom logo design & дизайн логотипа и фирменного стиля
Многолетний опыт. Огромное портфолио. Уникальное предложение и цена.
профессиональная рекламная фотография
креативно, смело, качественно
Custom logo design & рекламный креатив. дизайн рекламы
Многолетний опыт. Огромное портфолио. Уникальное предложение и цена.

НОУ ІНТУЇТ | лекція | Алгоритми: машини Тьюринга

  1. Основні визначення

Наша взаимовыгодная связь https://banwar.org/

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

Основні визначення

Вже згадана в цьому розділі модель алгоритмів була запропонована англійським математиком Тьюрингом в 1937 р ще до створення сучасних комп'ютерів1 Він виходив із загальної ідеї моделювання роботи обчислювача, що оперує відповідно до деякого суворим приписом. У машині Тьюринга розчленовування процесу обчислення на елементарні кроки доведено в даному разі до межі. Елементарним дією є заміна одного символу в комірці на інший і переміщення до сусідньої осередку. При такому підході процес обчислення значно подовжується, але зате логічна структура процесу сильно спрощується і набуває зручний для теоретичного дослідження вид.

Машина Тьюринга (м.т.) складається з необмеженої в обидві сторони стрічки, розбитою на осередки, по якій пересувається головка машини. Така "нескінченність" стрічки є математичною абстракцією, що відбиває потенційну необмеженість пам'яті обчислювача. Зрозуміло, в кожному завершується обчисленні використовується тільки кінцева частина цієї пам'яті - кінцеве число осередків. У кожному осередку стрічки записаний один символ з кінцевого зовнішнього алфавіту машини Машина Тьюринга (м . Головка машини являє кінцевий автомат, який в кожен момент часу знаходиться в одному з внутрішніх станів Q = {q0, q1, ..., qn}. На кожному кроці головка в залежності від свого внутрішнього стану і символу в комірці, яку вона спостерігає, змінює свій внутрішній стан і вміст спостерігається осередки і може зрушити на одну клітинку вправо або вліво або залишитися на місці.

Дамо більш формальне визначення.

Визначення 9.1. Машина Тьюринга - це система виду

що включає наступні компоненти:

Виділимо в алфавіті Виділимо в алфавіті   спеціальний порожній символ   і будемо вважати, що у всіх осередках стрічки, крім кінцевого їх числа, в початковий і в усі наступні моменти знаходиться порожній символ спеціальний порожній символ і будемо вважати, що у всіх осередках стрічки, крім кінцевого їх числа, в початковий і в усі наступні моменти знаходиться порожній символ.

Будемо говорити, що деякий символ стирається, якщо він замінюється на порожній. Два слова з Будемо говорити, що деякий символ стирається, якщо він замінюється на порожній будемо вважати рівними, якщо вони збігаються після відкидання всіх порожніх символів зліва і справа. наприклад, , але .

Як і для кінцевих автоматів, програму P можна задавати за допомогою таблиці розміру nxm, рядки якої відповідають станам з Q, а стовпці - символам з вхідного алфавіту Як і для кінцевих автоматів, програму P можна задавати за допомогою таблиці розміру nxm, рядки якої відповідають станам з Q, а стовпці - символам з вхідного алфавіту   в якій на перетині рядка qi і шпальти aj варто трійка qk al C - права частина команди qi aj -> qk al C в якій на перетині рядка qi і шпальти aj варто трійка qk al C - права частина команди qi aj -> qk al C.

Визначення 9.2. Назвемо конфігурацією М.Т. Визначення 9 в певний момент часу слово K = Wл qi aj Wп, де - слово на стрічці лівіше текушего положення головки, qi - внутрішній стан в даний момент, aj - символ, оглядає головкою, - слово на стрічці правіше текушего положення головки.

Будемо вважати, що слово Wл aj Wп містить всі значущі символи на стрічці. Тому, з точністю до описаного вище рівності слів, конфігурація визначена однозначно. Зокрема, якщо Будемо вважати, що слово Wл aj Wп містить всі значущі символи на стрічці , Тобто порожньо, то лівіше положення головки все осередки порожні, а якщо , То правіше положення головки все осередки порожні.

Початкова конфігурація - це конфігурація виду q0w, тобто в початковий момент часу головка в стані q0 оглядає перший символ вхідного слова w. {It Заключна} конфігурація - це конфігурація виду w1 qf w2, в якій машина знаходиться в заключному стані qf.

Визначення 9.3. Скажімо, що конфігурація K = w1 qi aj w2 м.т. Визначення 9 за один крок (такт) переходить в конфігурацію , Якщо в програмі є команда qi aj -> qk al C і при цьому,

Як завжди, через Як завжди, через   позначимо рефлексивне і транзитивне замикання відношення   а   буде означати, що конфігурація K за n кроків переходить в K ' позначимо рефлексивне і транзитивне замикання відношення а буде означати, що конфігурація K за n кроків переходить в K '. (Якщо з контексту ясно, про яку машину йде мова, то індекс будемо опускати).

Приклад 9.1.


Мал.9.1.

Виконання команди q3 0 -> q5 1 П

Наприклад, ситуації, представленої на рис.9.1 зліва відповідає конфігурація Наприклад, ситуації, представленої на   рис . Припустимо, що програма P містить команду q30 -> q51 П. Тоді після виконання цієї команди K перейде за один крок в конфігурацію , Показану на цьому малюнку праворуч. отже, .

Визначення 9.4. Обчислення м.т. Визначення 9 на вході w - це кінцева або нескінченна послідовність конфігурацій така, що K0 = q0w - початкова конфігурація. Ця послідовність кінцева, коли її остання конфігурація Kn = v1 qf v2 - заключна. У цьому випадку обчислення назвемо результативним, а слово v = v1 v2 - його результатом на вході w (завжди будемо припускати, що v не містить порожніх символів зліва і справа).

Визначення 9.5. Скажімо, що м.т. Визначення 9 обчислює часткову словникову функцію якщо для кожного слова w з області визначення f існує результативне обчислення з результатом , А якщо f (w) не визначена , То обчислення на вході w нескінченно.

Скажімо, що дві м.т. Скажімо, що дві м і еквівалентні, якщо вони обчислюють однакові функції.

Далі ми будемо також розглядати обчислення арифметичних функцій, тобто функцій з натуральними аргументами, які приймають натуральні значення. Для подання натуральних чисел використовуємо унарное кодування: число n буде представлятися як слово з n паличок | n, а послідовні аргументи будемо відокремлювати *.

Визначення 9.6. Скажімо, що м.т. Визначення 9 обчислює часткову арифметичну функцію f: Nk -> N, якщо для будь-якого набору чисел (x1, x2, ..., xk), на якому f визначена, існує результативне обчислення на вході з результатом , а якщо , То обчислення на відповідному вході нескінченно.

Аналогічне визначення можна дати і для інших спосбов кодування чисел (двійкового, десяткового і ін.). Нижче ми покажемо, що клас обчислюваних функцій не залежить від вибору одного з таких кодувань.

Категории
  • Биология
  • Математика
  • Краеведению
  • Лечебная
  • Наука
  • Физике
  • Природоведение
  • Информатика
  • Новости

  • Новости
    https://banwar.org/
    Наша взаимовыгодная связь https://banwar.org/. Запустив новый сайт, "Пари Матч" обещает своим клиентам незабываемый опыт и возможность выиграть крупные суммы.


    Наши клиенты
    Клиенты

    Быстрая связь

    Тел.: (044) 587-84-78
    E-mail: [email protected]

    Имя:
    E-mail:
    Телефон:
    Вопрос\Комментарий: