Pytania otagowane jako computation-models

Definicja zbioru dopuszczalnych operacji używanych do obliczeń i odpowiadających im kosztów. Niektóre przykłady modeli obejmują maszyny Turinga, funkcje rekurencyjne, rachunek lambda i systemy produkcyjne.

2
Czy możliwe jest sortowanie liczb całkowitych w O (n) w modelu transdychotomicznym?
Według mojej wiedzy nie istnieje algorytm najgorszego przypadku, który rozwiązuje następujący problem:O ( n )O(n)O(n) Biorąc pod uwagę ciąg długości składający się ze skończonych liczb całkowitych, znajdź permutację, w której każdy element jest mniejszy lub równy jego następcy.nnn Ale czy istnieje dowód, że nie istnieje, w transdychotomicznym modelu obliczeniowym ? …
2
Czy istnieje jasna definicja „obliczalnego” dla modeli obliczeniowych, które nie są kompletne?
Jest to kontynuacja kolejnego pytania tutaj i mam nadzieję, że nie jest to zbyt filozoficzne. Jak zauważył Raphael w komentarzu do mojego poprzedniego pytania, tak naprawdę nie rozumiem definicji „obliczalnego”, ale zgodnie z niektórymi artykułami, które czytam, definicja nie jest również bardzo jasna, jeśli chodzi o modele obliczeń słabsze niż …
2
Komputery analogowe i teza Kościoła Turinga
Chciałbym zacytować Nielsen & Chuang, Obliczenia kwantowe i informacje kwantowe, wydanie z okazji 10. rocznicy, strona 5 (moje wyróżnienie): Jedna klasa wyzwań dla silnej tezy Kościoła i Turinga pochodzi z dziedziny obliczeń analogowych. Przez lata od Turinga wiele różnych zespołów naukowców zauważyło, że niektóre typy komputerów analogowych mogą skutecznie rozwiązywać …
6
Czy maszyny Turinga zakładają kiedyś coś nieskończonego?
W poprzednim pytaniu Czym dokładnie jest algorytm? , Zapytałem, czy posiadanie „algorytmu”, który zwraca wartość funkcji opartej na tablicy wstępnie obliczonych wartości, jest algorytmem. Jedną z odpowiedzi, która zwróciła moją uwagę, była ta: Przykład silni wchodzi w inny model obliczeń, zwany obliczeniami nierównomiernymi. Maszyna Turinga jest przykładem jednolitego modelu obliczeniowego: …
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.