Hacker News new | past | comments | ask | show | jobs | submit login

Maybe I'm taking this a step too far but doesn't Gödel's Incompleteness Theorems (https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_...) state that a language can not define itself? You need a meta language to be able to define and specify a language in its entirety.

In other words, regex can not parse regex in its entirety. It's impossible.




Can a C program parse C source code? A Java program parse Java source code? Yes, they can, so such a general limitation couldn't be the reason regular expressions can't parse themselves.

Perhaps you had in mind the Halting Problem: https://en.wikipedia.org/wiki/Halting_problem#G%C3%B6del's_i...


No, not really. This is probably closer to Chomsky's area than Gödel's. Gödel's theorem is about semantics, not syntax.

As a nice counter-example to what you said, you can define the Backus-Naur notation using Backus-Naur notation: https://en.wikipedia.org/wiki/Backus%E2%80%93Naur_form#Furth...




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

Search: