Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Деякі операції над МТ

Читайте также:
  1. Господарські операції з обліку руху матеріальних цінностей бюджетних установ
  2. Господарські операції за січень 2011 року
  3. Деякі властивості, пов’язані з визначеними інегралами
  4. Деякі застосування рядів
  5. Елементарні операції паблік рилейшнз
  6. Кампанія з паблік рилейшнз та елементарні операції ПР

Робота МТ повністю визначається стартовим станом стрічки та логічного блока.

Нагадаємо, що композицією двох функцій та є функція

Означення.

Композицією МТ М1 та М2 є дві машини Тюрінга, що мають спільний зовнішній алфавіт та різні внутрішні алфавіти та

Композицією машин М1 та М2 є машина М, що має зовнішній алфавіт

та внутрішній і програмою, що створюється так:

У всіх командних символах , а інші символи залишаються без змін.

У всіх командах символи замінюються на відповідні .

При такій заміні машини М1 та М2 діють послідовно, по черзі обчислюючи та міняючи стрічку.

Так от, якщо та є функції, що можуть обчислюватись МТ то і їх композиція також може бути обчисленою.

 

Машина Тюрінга володіє універсальністю. Було доведено, що МТ може обчислити довільну функцію, лише б вона була обчислюваною.

Часто не є відомості в про обчислюваність МТ даної функції.

Виникає проблема її зупинки. Так от існує теорема, що не існує МТ такої, що могла б зупинити задану.

 


Дата добавления: 2015-07-15; просмотров: 142 | Нарушение авторских прав


Читайте в этой же книге: ВСЕВИДЯЩЕЕ ОКО 1 страница | ВСЕВИДЯЩЕЕ ОКО 2 страница | ВСЕВИДЯЩЕЕ ОКО 3 страница | ВСЕВИДЯЩЕЕ ОКО 4 страница | ВСЕВИДЯЩЕЕ ОКО 5 страница | В СМУТНЫЕ ВРЕМЕНА | ВДОВСТВУЮЩАЯ ЖЕЛЕЗНАЯ ЛЕДИ | МАСТЕР ЭМЕРИТУС [ [150]] ВСПОМИНАЕТ ВЕЛЛИНГТОНА | ДЖОН КИТС НА ХАФ-МУН-СТРИТ | ПРОЩАЛЬНАЯ ПОЭМА |
<== предыдущая страница | следующая страница ==>
Означення.| І. ВСТУП

mybiblioteka.su - 2015-2024 год. (0.007 сек.)