5
일부 프로그래밍 문제는 튜링 기계의 모든 기능을 필요로하지 않습니다. 그들은 훨씬 적은 힘으로 해결할 수 있습니다. 나는 더 적은 힘으로 프로그래밍 언어를 찾고있다. 스택에서 스택 팝 값에 값을 밀어 작업에결정 론적 푸시 다운 오토 마트의 힘을 가지며 더 이상 사용할 수없는 프로그래밍 언어가 있습니까?
스택 :
은 이러한 기능을 지원하기 위해 제한되는 높은 수준의 프로그래밍 언어가 존재한다.
값을 입력하고, 상태에서 상태로 이동하고, 스택과 상호 작용하고 결과를 출력하는 유한 상태 기계 (FSM).
은 내가 (등) Java 또는 C 나 파이썬을 사용하여 단지 스택과 FSM을 사용하는 프로그램을 작성하여 언어를 제한 할 수 있다는 것을 알고 있습니다. 그러나, 나는 단지 이러한 기능을 갖춘 프로그래밍 언어를 찾고 있습니다.
즉, 결정 론적 푸시 다운 오토 마트의 힘 만 필요로하는 문제를 해결하기 위해 Turing-complete 프로그래밍 언어를 사용하고 싶지 않습니다. 결정 론적 푸시 다운 오토 마트의 힘을 가진 프로그래밍 언어 만 사용하고 싶습니다.
질문자가 효율성을 찾고있는 것이 아니라 대신 Turing Machine보다 적은 전력으로 계산 모델을 사용하여 제공되는 멋진 속성입니까? 어쩌면 그는 튜링 머신으로 결정할 수없는 자신의 프로그램의 속성을 추론 할 수 있기를 기대했지만 덜 강력한 계산 모델에 대해서는 결정할 수있을 것입니다. – Guildenstern
좋은 지적, 감사합니다! 제 생각에 그 대답은 아마도 "아마도 그 작은 힘을 가진다면 아마 프로그래밍 언어라고 부르지 않을 것"이라고 다시 돌아갈 것이라고 생각합니다. 좋은 예제를 찾을 수는 없지만, 이런 종류의 "접착제"언어 또는 간단한 스크립팅 엔진에서이 종류를 발견 할 수 있을지도 모릅니다. 정규 표현식은 (단순한 형태로) 유한 상태 기계와 정식으로 동등합니다. 이 질문은 http://stackoverflow.com/questions/315340/practical-non-turing-complete-languages에 흥미로운 해답이 있습니다. – akroy