Регистрирайте сеРегистрирайте се

задача от разрешимост


 
   Форум за математика Форуми -> Дискретната математика
Предишната тема :: Следващата тема  
Автор Съобщение
КрТоР
Начинаещ


Регистриран на: 10 Aug 2009
Мнения: 1
Местожителство: stud.grad

МнениеПуснато на: Tue Aug 11, 2009 12:43 pm    Заглавие: задача от разрешимост

Моля ако някои знае трябва ми помош за тя задача

зад: Нека R и P са полуразрешими езици над {a,b} за които {a,b}*\(R U P) и R ∩ P са крайни.
1)Докажете че R e разрешимо множество.
2)Покажете че множеството от кодовете на Машината на Тюринг М, за който L(M) = P, не е разрешимо.

мерси предварително Smile
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Реклама







Пуснато на:     Заглавие: Реклама

Върнете се в началото
masterfromkardjali
Начинаещ


Регистриран на: 30 Oct 2006
Мнения: 35

Репутация: 14.7

МнениеПуснато на: Thu Aug 20, 2009 2:43 pm    Заглавие:

R ⊆A (alphabet) е ( разрешимо), ако характеристичната му функция е изчислима.Съществува Tюринг машина, която може да реши дали дадена дума е от езика (а,b)* => Характеристичната функция е изчислима => R e разрешимо множество.

Множеството от кодовете на Машината на Тюринг М, за който L(M) = P <=> Р е език еквивалентен на Тюринг машината. Твоята Тюринг машина не може да реши дали даден език е еквивалентен на нея самата => неразрешимост.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Покажи мнения от преди:   
   Форум за математика Форуми -> Дискретната математика Часовете са според зоната GMT + 2 Часа
Страница 1 от 1

 
Идете на:  
Не Можете да пускате нови теми
Не Можете да отговаряте на темите
Не Можете да променяте съобщенията си
Не Можете да изтривате съобщенията си
Не Можете да гласувате в анкети
You cannot attach files in this forum
Може да сваляте файлове от този форум
Copyright © 2005-2021 math10.com.