I wonder if those 'irregular expressions' are already lambda isomorph (or say Tu... | Hacker News

Hacker Newsnew | past | comments | ask | show | jobs | submit

		eru on Sept 24, 2007 \| parent \| context \| favorite \| on: A regular expression to check for prime numbers I wonder if those 'irregular expressions' are already lambda isomorph (or say Turing complete if you like).

cperciva on Sept 25, 2007 [–]

No. Regular expressions plus backwards references is in NP; Turing machines can solve far more difficult decision problems.

eru on Sept 25, 2007 | [–]

Yes, they can. I was just to lazy to look this up myself. Thanks.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact