(Jak) Czy możemy odkryć / przeanalizować problemy NP przy braku modelu obliczeniowego Turinga?

Z czysto abstrakcyjnego punktu widzenia rozumowania matematycznego / obliczeniowego (jak) można nawet odkryć lub wyjaśnić problemy takie jak 3-SAT, suma częściowa, podróżny sprzedawca itp.,? Czy bylibyśmy w stanie w jakikolwiek sensowny sposób uzasadnić je tylko z funkcjonalnego punktu widzenia? Czy to w ogóle możliwe?

Zastanawiam się nad tym pytaniem wyłącznie z punktu widzenia samego siebie w ramach uczenia się modelu obliczeniowego rachunku lambda. Rozumiem, że jest to „nieintuicyjne” i dlatego Godel faworyzował model Turinga. Chciałbym jednak wiedzieć, jakie są znane teoretyczne ograniczenia tego funkcjonalnego stylu obliczeń i na ile stanowiłoby to przeszkodę w analizie problemów klasy NP?

Możesz spojrzeć na semantykę kosztów dla języków funkcjonalnych . Są to różne miary złożoności obliczeniowej dla języków funkcjonalnych, które nie przechodzą przez żadną maszynę Turinga, maszynę RAM itp. Dobrym miejscem do rozpoczęcia wyszukiwania jest ten post Lambda Ultimate , który ma kilka dobrych referencji.

Sekcja 7.4 praktycznych podstaw języka programowania Boba Harpera wyjaśnia semantykę kosztów.

Artykuł na temat względnej przydatności kul ognistych Accattoli i Coena pokazuje, że rachunek ma co najwyżej liniowy wybuch w stosunku do modelu maszyny RAM.$\lambda$

Podsumowując, na tej innej planecie sytuacja byłaby prawie taka sama w odniesieniu do NP, ale byłoby mniej przepełnień bufora i nie byłoby tak dużo śmieci wokół.

Na prośbę dr Andreja i doktora zmieniam swój komentarz w odpowiedź, przepraszając za autoreklamę.

Niedawno napisałem papieru , w którym patrzę na jak udowodnić twierdzenie Stoły Levin ( -completeness z SAT) za pomocą języka funkcjonalnych (wariant X-rachunku) zamiast maszyn Turinga. Podsumowanie:$\mathsf{NP}$

• kluczowym pojęciem jest przybliżenie afiniczne, tzn. przybliżenie dowolnych programów przez programy afiniczne (które mogą wykorzystać swoje dane wejściowe najwyżej); intuicja jest taka, że $$\frac{\text{Boolean circuits}}{\text{Turing machines}}=\frac{\text{affine $\lambda$-terms}}{\text{$\lambda$-terms}}$$ $\lambda$
• $\lambda$
• $\mathsf{NP}$
• oczywiście można wówczas zredukować HO CIRCUIT SAT do CIRCUIT SAT, dowodząc w ten sposób zwykłego twierdzenia Cooka-Levina, a krwawe szczegóły na niskim poziomie są przenoszone na budowę takiej redukcji.

$\mathsf{NP}$

$\lambda$$\lambda$

$\mathsf{NP}$

$\lambda$

$\lambda$

$\mathsf{NP}$$\mathsf{NP}$$\mathsf{coNP}$$\lambda$

$\lambda$$\lambda$

$\mathsf{NP}$$\lambda$, nie ma znaczenia, czy wiesz, że twoje intuicje są prawidłowe. Maszyny Turinga dały natychmiastową, wykonalną odpowiedź, a ludzie nie (i nadal nie) czuli potrzeby pójścia dalej.