16

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.

4
  • @PhilipKendall That is a valid (if degenerate) answer. Of course almost all programs will immediately JMP into unknown space and crash. But that doesn't mean they aren't meaningful. Reminds me of superoptimzation.
    – mp-
    Dec 24, 2018 at 7:19
  • Suppose you have a trivial language when given a letter ascii it prints it and moves onto the next character. That technically satisfies your definition. Any input is valid. It would be a rather silly language as you can't do anything productive with it, but of course we're not talking about practicality.
    – Neil
    Dec 24, 2018 at 7:24
  • 1
    @Neil: that is not a Turing-complete language.
    – Doc Brown
    Dec 24, 2018 at 10:35
  • I've heard this about APL, but I'm not sure if it is true, might have been true once upon a time, or is merely a comic exaggeration. Snippets of APL I've seen online don't bear evidence against it, though...
    – trent
    Mar 11, 2021 at 22:18

5 Answers 5

12

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":

  • what happens if it jumps outside the initialized space?
  • How does the "program" terminate anyway?
2
  • 2
    "what happens if it jumps outside the initialised space" - by simply adding a rule "jumps to adress 0 in this case", it should be quite simple to handle. Should not be too hard to define some extra semantics for deailing with those edge cases.
    – Doc Brown
    Dec 24, 2018 at 10:26
  • 2
    jumps outside initialised space is syntactically valid, and possibly even semantically valid as well (e.g. its well defined semantics is to produce a segfault).
    – Lie Ryan
    Dec 24, 2018 at 11:47
10

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.

4
  • 5
    Also, since any non-whitespace character is ignored as a comment, not just every permutation of whitespace, but in fact every permutation of ASCII characters is also syntactically valid. Dec 24, 2018 at 9:00
  • 2
    To be nitty: having a short look into the Whitespace tutorial, it seems a stack manipulation [Space] must not be followed by a [Tab] character. But I guess it will be simple to extend the language for these special cases (for example, by giving them No-Op semantics).
    – Doc Brown
    Dec 24, 2018 at 10:47
  • @docbrown, in the examples I do see sequences of [Space][Tab], so I am not sure where you got your conclusion from. Dec 24, 2018 at 13:04
  • 1
    @BartvanIngenSchenau: look into the tutorial: a stack manipulation is introduced by a [Space] followed by one of four possible commands, which start either with another [Space] or [LF]. The sequence [Space][Tab] can occur as part of a number, or as part of a different command, of course, but a [Tab] is not a valid character after a stack command introduced by [Space] .
    – Doc Brown
    Dec 24, 2018 at 13:13
0

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.

4
  • "bits are so 20th century computerish": What do you mean by this?
    – Giorgio
    Dec 24, 2018 at 12:51
  • I mean strings, characters and bits are a technical detail, essentially you are talking about instructions and operants. How those are implemented is irrelevant to the question. Dec 24, 2018 at 13:50
  • Yes, but this observation was true even 50 years ago (formal languages are even older), so I am still not sure I understand what you mean.
    – Giorgio
    Dec 24, 2018 at 17:19
  • 1
    I just wanted to bring down the question to its logical essence. It is not about strings or bytes, it is about instructions and arguments. Can you mix those up in an arbitrary way and be sure to get a valid program? Dec 24, 2018 at 19:41
0

If you reduce the question to a language for which all characters it accepts are valid programs, Brainfuck does this.

https://gsurma.medium.com/meta-intelligence-writing-programs-that-write-programs-part-1-genetic-evolution-679b65c37c5f

There are only 8 characters, all of them are valid operations, so randomly generated strings of these 8 characters are all valid programs.

2
  • 2
    If you only have an opening brace and no closing brace is it a valid program? Mar 11, 2021 at 21:39
  • @JerryJeremiah No. But it could be interesting to explore how to extend the language so that unmatched brackets are still syntactically valid and preferably also carry some semantics. For comparison, according to Wikipedia, the runtime error of invalid memory access is treated differently by implementation, e.g. by using the address modulo the memory size. May 24, 2021 at 13:59
0

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.