Форум за въпроси

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

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

by Марио Ничев -
Number of replies: 2

Може ли малко разяснения за:

  • "композиция на две машини на Тюринг
  • разклонение на две машини на Тюринг относно трета
  • функция, която връща машина на Тюринг, реализираща while-цикъл над дадената машина на Тюринг"
За композицията предполагам двете ленти на машините се сливат и се извърша първата и след това втората функция? 
За другите две не знам какво се очаква да извърши програмата.
In reply to Марио Ничев

Re: Машина на Тюринг

by Трифон Трифонов -
И трите понятия са взети директно от лекциите ви по ЕАИ. Все пак, ето разяснения:

  • композиция означава втората машина на Тюринг да работи върху резултата от първата
  • разклонение на две машини на Тюринг S и T относно трета машина B означава: да се изпълни B и ако резултатът е "истина" (т.е. ненулев) да се изпълни S, в противен случай да се изпълни T.
  • за while цикъл идеята е следната: изпълнявай дадена машина на Тюринг T и всеки път проверявай дали след изпълнението главата сочи върху 1 или 0. При 1 - ново повторение, при 0 - край.