Automat niedeterministyczny - ile elementów ma zbiór


(Kamilu852) #1

Jest ktoś wstanie odpowiedzieć mi na pytanie ? bo szukam już dosyć długo w internecie i nie znalazłem konkretnej odpowiedzi.

 

Ile elementów ma zbiór problemów obliczalnych automatami niedeterministycznymi,

ale nieobliczalnych automatami deterministycznymi ?


(kostek135) #2

Bo tego nie trzeba szukać tylko przeprowadzić matematyczny dowód formalny, odpowiedź jest trywialna.


(Kamilu852) #3

Wiem, że w książkach pewnie znalazł bym odpowiedź, ale w internecie tego nie ma a odpowiedzi potrzebuję na wczoraj. Mogłbyś mi pomóc ?


(kostek135) #4

Poszukaj tutaj: http://www.issi.uz.zgora.pl/pl/didactic/sawerwain/tpi/t-fund-of-cs-lec07-4on1.pdf