Для правильной и ограниченной задачи, четко и корректно сформулированной, Вы не сможете написать программу, ее решающую.
Если мне запретят использовать часть из возможных функций, ограничив Прологом, то конечно не смогу. Хотя, даже если там реализуемы все они, то:
Вы доработаете Ваш интерпретатор, но найдется новый глюк. И так до бесконечности.
- вот про бесконечность забудьте. Если мне скажут максмально допустимую длину входных данных и дадут подходящий компьютер, безглючная программа будет написана.
Мы немного запутались, видимо, слишком торопимся. Уточняю.
1.
Правильная и ограниченная задача, четко сформулированная - это программа на языке Пролог (сейчас точно не помню, примерно 50 или 100 строк, т.е. по программистким меркам совсем маленькая). Эта Пролог-программа представляет собой вполне понятное и очевидное логическое описание рассматриваемой задачи. Уверяю Вас, что, посмотрев на эту Пролог-программу, Вы все согласитесь, что она понятно и четко описывает логику задачи. И четко определяет какой ответ надо давать на любой запрос к этой Пролог-программе.
2. А теперь Вас просят написать транслятор (компилятор или интерпретатор, последнее более типично для Пролога) для языка Пролог. И
Вас ничем не ограничивают! Даже длиной данных. Вы, разумеется, напишете транслятор.
3. И представьте себе ужас Вашего положения - вам тычут ... глюк.
4. Вы его устраняете, а Вам ... новый глюк.
За подробностями отсылаю к литературе. Например, см. старую книгу "Представление в ЭВМ неформальных процедур" (дайте поиск в Яндексе).
P.S. Я оказался в положении Д'Артаньяна. Поэтому приношу извинения остальным участникам за то, что не могу сразу ответить всем - буду делать это постепенно.