Pytania otagowane jako turing-completeness

9
Dlaczego niektóre języki programowania Turing są kompletne, ale brakuje im umiejętności innych języków?
Napotkałem dziwny problem podczas pisania interpretera, który (powinien) zaczepia się o zewnętrzne programy / funkcje: Funkcje w „C” i „C ++” nie mogą przechwytywać funkcji variadic , np. Nie mogę utworzyć funkcji, która wywoła „printf” z dokładnie tymi samymi argumentami, które otrzymał, i zamiast tego musi wywołać alternatywną wersję, która …
9
Czy C faktycznie Turinga jest kompletny?
Próbowałem wyjaśnić komuś, że C jest kompletne w Turinga, i zdałem sobie sprawę, że tak naprawdę nie wiem, czy w rzeczywistości jest to kompletny Turing. (C jak w semantyce abstrakcyjnej, a nie jak w rzeczywistej implementacji). „Oczywista” odpowiedź (z grubsza: może zająć się dowolną ilością pamięci, więc może emulować maszynę …
5
Co oznacza bycie kompletnym Turinga?
Widzę, że większość definicji tego, co ma być Turing-zupełne, jest do pewnego stopnia tautologiczna. Na przykład, jeśli Google „co oznacza bycie kompletnym Turinga”, otrzymuje: Komputer jest kompletny, jeśli może rozwiązać każdy problem, który maszyna Turinga może ... Chociaż jest bardzo dobrze określone, czy różne systemy są Turinga kompletne, czy nie, …
7
Czy wszystkie języki są kompletne wymienne?
Uwaga: chociaż umiem programować, jestem całkiem początkującym w teorii CS. Zgodnie z tą odpowiedzią Kompletność Turinga jest abstrakcyjną koncepcją obliczalności. Jeśli język jest kompletny Turinga, jest on w stanie wykonać dowolne obliczenia, które może wykonać każdy inny kompletny język Turinga. I każdy program napisany w dowolnym języku kompletne Turinga mogą …
1
Czy pętla „do while” jest wystarczająca dla kompletności Turinga?
Wiem, że w imperatywnych językach programowania pętla while-do jest wystarczająca jako konstrukcja przepływu sterowania, aby uzupełnić język Turinga (jeśli chodzi o przepływ sterowania - oczywiście potrzebujemy również nieograniczonej pamięci i niektórych operatorów ...) . Istota mojego pytania brzmi: czy pętla „do-while” ma taką samą moc obliczeniową jak pętla „do-do”? Innymi …
5
Dlaczego języki funkcjonalne Turing są kompletne?
Być może moje ograniczone rozumienie tematu jest nieprawidłowe, ale rozumiem do tej pory: Programowanie funkcjonalne oparte jest na rachunku Lambda Calculus opracowanym przez Alonzo Church. Programowanie imperatywne oparte jest na modelu maszyny Turinga, stworzonym przez Alana Turinga, ucznia Churcha. Rachunek Lambda jest tak potężny i zdolny jak Maszyna Turinga, co …
1
Czy istnieje kompletny problem dla klasy rozstrzygających problemów Turinga?
Języki, takie jak są uzupełniane ponownie przy wielu redukcjach. To banalne, aby zobaczyć, że co-RE ma również kompletne problemy. S. Schmitz [1] rozważa niektóre klasy pomiędzy ELEM a REC . Stanowią one kompletne problemy dla tych klas w ramach specjalnie spreparowanych redukcji.HALTTMHALTTM\text{HALT}_{TM}RE-completeRE-complete\textsf{RE-complete}co-REco-RE\text{co-RE}ELEMELEM\text{ELEM}RECREC\text{REC} Czy istnieją całkowite problemy dla (aka REC ) …
2
Czy funkcje wyższego rzędu zapewniają większą moc programowaniu funkcjonalnemu?
Zadałem podobne pytanie na cstheory.SE . Zgodnie z tą odpowiedzią na Stackoverflow istnieje algorytm, który w nieliniowym czystym funkcjonalnym języku programowania ma złożoność , podczas gdy tym samym algorytmem w programowaniu imperatywnym jest Ω ( n ) . Dodanie lenistwa do języka FP spowodowałoby, że algorytm Ω ( n ) …
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.