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

Означення.

Обчислюваність за Тюрінгом

Цікаво, чи існують функції, які можуть бути обчислені за даним способом. Адже з самого початку ми задаємо стрічку з функцією, яку необхідно обчислити. Якщо ми здійснимо операції обчислення то відповідь буде на стрічці. Кожне натуральне число “n” кодуємо як “n+1”, бо є 0, який закодувати неможливо за допомогою 1.

Тоді числа

0, 2, 1, 3, 4

1, 11, 111, 1111 і т.д. кодуються на стрічці.

 

Означення.

Часткова числова n – містна функція називається обчислюваною за Тюрінгом, якщо існує машинам, яка обчислює її таким чином:

  1. Якщо набір аргументів належить області визначення функції машина М починає роботу в конфігурації стрічки

завершає роботу в конфігурації

де “у” – відповідь.

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

 


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


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

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