logotip ua5.org
UA5.ORG

Методичні матеріали з інформатики
 
 
      Головна Зв'язок Статистика Закладки Пошук      
 
 
 
Розділи
 

Популярні публікації
 

Рекомендовані матеріали
 

Рекламні матеріали
 

 

Машина Тьюринга


Основні поняття інформатики
     
     
   
 

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

У кожнім гнізді стрічки може стояти будь-який символ із заданого алфавіту, у якім виділений «порожній» символ — ознака того, що гніздо порожнє.

Машина має кінцеву безліч внутрішніх станів, початкове (з нього починається робота машини) і кінцевий стан, потрапивши в яке машина припиняє роботу.

 Крім стрічки є головка читання/запису, який уміє рухатися вперед, назад і стояти на місці; уміє читати вміст, стирати й записувати символи з даного алфавіту; управляється програмою.

Програма — це таблиця, у якій у кожній клітці записана команда. Кожна клітка визначається двома параметрами — символом алфавіту й станом машини. Команда — ця вказівка, куди пересунути головку читання/запису з поточного стану, який символ записати в поточне гніздо й у який стан перейде машина.

Машина Тьюринга — це модель комп'ютера.

Машина одержала ім'я математика А. Тьюринга (Англія) і вирішує наступну проблему: якщо для рішення завдання можна побудувати машину Тьюринга, вона алгоритмічно розв'язна.

І машина Тьюринга, і машина Поста еквівалентні по своїх можливостях.

Розроблені практично в те саме час (в 1936 р.) незалежно друг від друга.

чи Можна будь-який алгоритм представити у формі машини Тьюринга? Відповідь на це питання дається у вигляді так званого тези Тьюринга: усякий алгоритм представимо у формі машини Тьюринга. Це теза тому, що його неможливо довести, тому що в ньому фігурують, з одного боку, інтуїтивне поняття «усякий алгоритм», а з іншого сторони — точне поняття «машина Тьюринга».

Клас нормальних алгоритмів Маркова й клас алгоритмів, представлених у формі машин Тьюринга, збігаються.
 
   
 
 
Інші статті за темою:

  • Машина Поста
  • Алгоритм
  • Машина Беббиджа
  • Алгоритми та їх властивості
  • Історія комп'ютера - початок ХХ століття


  •  
         
         

     
     
     
    Яндекс.Метрика
     

     
         
      Copyright © 2008-2016 UA5.org