Pytania otagowane jako undecidability

Pytania dotyczące problemów, których nie może rozwiązać żadna maszyna Turinga.

2
Rozstrzygalność sprawdzania pierwotnego?
Załóżmy, że mam dwie funkcje i i jestem zainteresowany ustaleniem, czyFFFGGG F(x)=∫G(x)dx.F(x)=∫G(x)dx.F(x) = \int G(x)dx. Załóżmy, że moje funkcje składają się z funkcji elementarnych (wielomiany, wykładnicze, logi i funkcje trygonometryczne), ale nie, powiedzmy, szereg Taylora. Czy można rozwiązać ten problem? Jeśli nie, czy jest to w połowie rozstrzygalne? (Pytam, ponieważ …
2
Rozstrzygalność języka przedrostka
W połowie kadencji istniała odmiana następującego pytania: Dla rozstrzygalnego zdefiniuj Pokaż, że niekoniecznie jest rozstrzygalny.LLLPref(L)={x∣∃y s.t. xy∈L}Pref(L)={x∣∃y s.t. xy∈L}\text{Pref}(L) = \{ x \mid \exists y \text{ s.t. } xy \in L\}Pref(L)Pref(L)\text{Pref}(L) Ale jeśli wybiorę to myślę, że jest również , a zatem jest rozstrzygalne. Również daje ten sam wynik. A …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.