Software Engineering Stack Exchange is a question and answer site for professionals, academics, and students working within the systems development life cycle. It only takes a minute to sign up.
Sign up to join this community
Does there exist a Turing complete programming language such that for a fixed alphabet (say, ASCII), every possible permutation of those characters is a semantically valid program capable of being executed?
We consider infinite loops to also be semantically valid.
I know some data formats, such as Markdown, possess universal semantic validity (every input is valid), but I cannot off-hand think of a programming language with this property.
Every octet sequence can be interpreted as valid Z80 code as there are no invalid opcodes or arguments; I imagine the same would apply to various other processors, I just personally know Z80.
For low-level things like this, you possibly start running into questions about what it means to "execute a program":
Such questions about programming languages are almost universally answered with yes. If there currently is no language that has the requested property, you can bet that someone will see it as a challenge to create a (toy) language that does have the property.
As an example of a language where every permutation of the alphabet's characters is syntactically valid is the whitespace language, where the alphabet of the language itself consists of space, tab and linefeed.
Why settle for strings (of characters)? You should rephrase that question to "any series of tokens". Not bits, bits are so 20th century computerish.
So, infinite loops are OK you say. What about division by zero? If you are lenient enough wjth your definition of valid you may get a yes but most combinations would still be meaningless. So I would say you may always get a technically valid program but hardly ever a semantically valid program.
If you reduce the question to a language for which all characters it accepts are valid programs, Brainfuck does this.
There are only 8 characters, all of them are valid operations, so randomly generated strings of these 8 characters are all valid programs.
Simple. Start with the C language. Now we build a compiler for a language C' which works like this: The compiler looks for the longest prefix of the program that could be extended to a valid C program, and ignores the rest of the program. Then it adds the shortest and alphabetically first string to that prefix which produces a valid C program, and translates the result using a C compiler. Obviously any program is valid.
Oh well. C is not turing complete. Add arbitrary large integers and pointers to make it turing complete.
