Czy język może być Turing-complete bez wsparcia dla tablic?

Question

Jeśli język ma struktury kontrolne i zmienne, ale nie obsługuje tablic, list, dostępu do pamięci i alokacji itp., Czy może to być Turing-complete?

Może gdyby nie było ograniczeń co do ilości zmiennych można tworzyć, można symulować tablice tworząc zmienne jak array_1, array_2 ... array_6000 i ręcznie pętli przez nich, i jakoś tworzenia złożonych struktur danych i rekursji?

Edycja: Nawet jeśli nie możesz uzyskać dostępu do zmiennych poprzez manipulację nazwami (array_10+i jest niedozwolone)?

Answer 1

Oczywiście. Spójrz na Lambda Calculus, który jest jednym z najbardziej minimalnych języków Turing Complete, jakie kiedykolwiek widziałem. Zasadniczo wszystko, co masz, to lambdas (literały funkcyjne); brak przydziału, brak deklaracji, brak struktur danych. Wszystko to bardzo mocno odchudzone.

Można jednak symulować liniową strukturę danych, taką jak lista, łącząc funkcje. Jest dość gadatliwy, ale z pewnością jest to możliwe i jest o wiele ładniejsze niż posiadanie dużej serii zmienn nazwanych sekwencyjnie.

Ogólnie rzecz biorąc, to, czy język jest Turing Complete nie ma nic wspólnego z tym, czy ma tablice. Języki funkcjonalne, takie jak SML i Haskell, pozbawione są tablic, podobnie jak Lambda Calculus, a są to właściwie użyteczne języki! Mówienie języka to "Turing Complete" to tylko inny sposób powiedzenia, że ​​nie ma funkcji Turing Computable, której nie można wyrazić we wspomnianym języku. Jest to zaskakująco luźna kwalifikacja, umożliwiająca wiele języków, które byłyby całkowicie niepraktyczne (jak Lambda Calculus).

Answer 2

Istnieje wiele języków z obsługą Turinga, które nie mają nawet pojęcia "zmiennej"! Dostęp do pamięci i alokacje to szczegóły implementacji, więc są całkowicie nieistotne. Musisz zdać sobie sprawę, że maszyny Turinga i kompletność Turinga są bardzo teoretycznymi koncepcjami, przydatnymi do udowodnienia rzeczy, ale całkowicie oderwanymi od rzeczywistości rzeczywistego sprzętu.

Paul Graham napisał długi, ale bardzo, bardzo interesujący essay historii języków programowania, gdzie opisuje on dwie bardzo różne główne tradycje języków komputerowych:

• Lisp, Scheme, itd. - pochodzi z teoretycznych rozważań, bardzo proste, ale z koncepcyjnie potężnymi językami, ale przez długi czas niepraktyczne z powodu ich zupełnego lekceważenia dla tego, co jest łatwe i efektywne w implementacji Asembler, FORTRAN, C i prawie wszystkie języki "głównego nurtu" - wyprowadzono więcej lub mniej bezpośrednio z tego, co może zrobić sprzęt, łatwe do wdrożenia, wydajne, ale dla najdłuższy czas niższej w stosunku do (starszej!) rodziny Lisp pod względem ekspresji.

Wygląda na to, że znacie tylko drugą tradycję, ale kompletność Turinga to koncepcja wywodząca się z tych samych zasad, co pierwsza tradycja, i nie ma sensu, jeśli nie znacie tych zasad.