Означення.

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

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

Тоді числа

0, 2, 1, 3, 4

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

Означення.

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

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

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

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

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

Дата добавления: 2015-07-15