Languages and Decidability
So, I don’t really have much formal training in linguistics, so this is most likely answered somewhere, but is infinite lookahead distinct from decidability?
Setting this up, I’m assuming knowledge of the Chomsky hierarchy and the halting problem.
Basically, we know that C++ parsing is undecidable, but I told someone that that is distinct from infinite lookahead, which I said was requiring an infinite number of symbols to disambiguate meaning.
Later, I correlated this with how regexes (regular expressions) would require an infinite amount of lookahead to be able to solve the matching braces problem, which is more easily resolved by moving up the hierarchy of languages, so it feels like “infinite lookahead” is just a symptom of “you’re too low in the language stack”. So if some “language” were to exist that always required infinite lookahead, would it be a language? (This is the actual question I have, woops.)
Feel free to send in threads/discussions/answers here. I’ll update this post as I explore/learn about stuff.