Niektóre problemy z programowaniem nie wymagają pełnej mocy maszyny Turinga do rozwiązania. Można je rozwiązać za pomocą znacznie mniejszej mocy. Szukam języka programowania z mniejszą mocą.Czy istnieje język programowania, który ma tylko moc deterministycznych automatów push-down, i nic więcej?
Czy istnieje taki język wysokiego poziomu, który jest ograniczony do wsparcia tylko tych możliwości:
stos z operacji popychają wartości na wartości stosu i zasnąć stosie.
Skończona maszyna stanów (FSM) do wprowadzania wartości, przechodzenia od stanu do stanu, interakcji ze stosem i wyników wyjściowych.
Zdaję sobie sprawę, że mogę używać Java lub C lub Python (itp) i ograniczyć język pisząc program, który używa tylko stos i FSM. Jednak szukam języka programowania, który ma takie możliwości i nic więcej.
Innymi słowy, nie chcę używać języka programowania Turinga, aby rozwiązywać problemy wymagające tylko deterministycznego automatyzmu wypychania. Chcę używać języka programowania, który ma tylko moc deterministycznych automatów push-down.
Może pytający nie szukał wydajności, ale zamiast tego ładne właściwości, które pochodzą z używania modelu obliczeniowego z mniejszą mocą niż maszyna Turinga? Może chciał dowiedzieć się o właściwościach swojego programu, które byłyby nierozstrzygalne dla maszyny Turinga, ale jest to rozstrzygające dla mniej wydajnego modelu obliczeniowego. – Guildenstern
Dobra uwaga, dziękuję! Myślę, że odpowiedź prawdopodobnie nadal wraca do "prawdopodobnie nie nazwałbyś tego językiem programowania, gdyby miał tak małą moc". Podejrzewam, że możesz znaleźć ten rodzaj w rodzaju "kleju" lub w prostych skryptach, chociaż nie mogę znaleźć dobrego przykładu. Wyrażenia regularne (w ich prostej postaci) są jednak kanonicznie równe dla skończonej maszyny stanów. To pytanie http://stackoverflow.com/questions/315340/practical-non-turing-complete-languages ma kilka interesujących odpowiedzi. – akroy