I read several times that HPSG and Minimalism are Turing-complete. Could someone explain (or tell me some references) why this is the case? And does this constitute a major problem since natural languages are widely considered mildly context-sensitive?

  • Addressing only the last question, if so then the machinery of these two theories is "too powerful", and you should choose a less powerful engine.
    – user6726
    Oct 23 at 23:37
  • So is LFG. It’s not really a problem per se but the formalisms are cumbersome for some syntactic constructions.
    – Atamiri
    Oct 24 at 14:07
  • @Atamiri Thank you for your reply! Would you have some resources/reading suggestions on that topic?
    – pahohu
    Oct 30 at 11:52
  • The only book on this topic I’m aware of is “Formal issues in LFG”. It summarises the contents of several unpublished technical reports written by Xerox PARC researchers.
    – Atamiri
    Oct 31 at 16:01
  • Thank you very much! I'll have a look.
    – pahohu
    Oct 31 at 22:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.