Регистрирайте се
Предишната тема :: Следващата тема |
Автор |
Съобщение |
КрТоР Начинаещ
Регистриран на: 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, не е разрешимо.
мерси предварително |
|
Върнете се в началото |
|
|
Реклама
|
Пуснато на: Заглавие: Реклама |
|
|
|
|
Върнете се в началото |
|
|
masterfromkardjali Начинаещ
Регистриран на: 30 Oct 2006 Мнения: 35
|
Пуснато на: Thu Aug 20, 2009 2:43 pm Заглавие: |
|
|
R ⊆A (alphabet) е ( разрешимо), ако характеристичната му функция е изчислима.Съществува Tюринг машина, която може да реши дали дадена дума е от езика (а,b)* => Характеристичната функция е изчислима => R e разрешимо множество.
Множеството от кодовете на Машината на Тюринг М, за който L(M) = P <=> Р е език еквивалентен на Тюринг машината. Твоята Тюринг машина не може да реши дали даден език е еквивалентен на нея самата => неразрешимост. |
|
Върнете се в началото |
|
|
|
|
Не Можете да пускате нови теми Не Можете да отговаряте на темите Не Можете да променяте съобщенията си Не Можете да изтривате съобщенията си Не Можете да гласувате в анкети You cannot attach files in this forum Може да сваляте файлове от този форум
|
|