Well in my book it is says that “there are non-decidable languages” And the proof is:
Every algorithm is a word. Then there are only countable algorithms. But there are uncountable languages and therefore more than algorithms
Why is it said that every algorithm is a word? A word is a concatenation of symbols, elements of an alphabet, then what’s the relation between a word and an algorithm? Can anyone explain me that?
2
Here’s a solid example.
Some languages have metaprogramming/preprocessing systems that contain code that needs to be evaluated at compile time. This can be simple substitution, like C’s macros, or more complex.
There are some cases in which the compile-time code evaluation system is complex enough that it can be shown to be Turing-complete. C++’s Template system is the most infamous example of this, though Perl and Lisp have also been shown to have this property.
One famous property of Turing-complete languages is the Halting Problem: it is possible to construct a valid program in any Turing-complete language which will end up in an infinite loop and not terminate. It is also possible, in any Turing-complete language, to construct a valid program for which it is not possible to determine whether or not it will end up in an infinite loop.
Since preprocessing code has to be evaluated to completion by the compiler, this means that in a programming language with Turing-complete compiler-time preprocessing, it is possible to construct a syntactically-correct program for which it is not possible for the compiler to decide what it means. Thus, C++, Perl and Lisp are non-decidable languages in the general case. (Which, of course, does not mean that it’s not possible to write programs in them. Just that not every syntactically correct program written in them can be understood by a parser.)
3