Is there a programming language where every string is a valid program?
Clash Royale CLAN TAG#URR8PPP
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.
programming-languages syntax turing-completeness
asked Dec 24 '18 at 6:06
mp-
471
add a comment |
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.
programming-languages syntax turing-completeness
asked Dec 24 '18 at 6:06
mp-
471
@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 '18 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 '18 at 7:24
@Neil: that is not a Turing-complete language.
– Doc Brown
Dec 24 '18 at 10:35
add a comment |
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.
programming-languages syntax turing-completeness
asked Dec 24 '18 at 6:06
mp-
471
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.
programming-languages syntax turing-completeness
programming-languages syntax turing-completeness
asked Dec 24 '18 at 6:06
mp-
471
asked Dec 24 '18 at 6:06
mp-
471
asked Dec 24 '18 at 6:06
mp-
471
asked Dec 24 '18 at 6:06
mp-
471
asked Dec 24 '18 at 6:06
mp-
471
471
@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 '18 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 '18 at 7:24
@Neil: that is not a Turing-complete language.
– Doc Brown
Dec 24 '18 at 10:35
add a comment |
@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 '18 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 '18 at 7:24
@Neil: that is not a Turing-complete language.
– Doc Brown
Dec 24 '18 at 10:35
@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 '18 at 7:19
@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 '18 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 '18 at 7:24
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 '18 at 7:24
@Neil: that is not a Turing-complete language.
– Doc Brown
Dec 24 '18 at 10:35
@Neil: that is not a Turing-complete language.
– Doc Brown
Dec 24 '18 at 10:35
add a comment |
3 Answers
3
active
oldest
votes
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?
edited Dec 30 '18 at 20:07
alecxe
18114
answered Dec 24 '18 at 8:06
Philip Kendall
6,31321926
1
"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 '18 at 10:26
1
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 '18 at 11:47
add a comment |
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.
answered Dec 24 '18 at 7:57
Bart van Ingen Schenau
49.4k979127
4
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.
– Jörg W Mittag
Dec 24 '18 at 9:00
1
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 '18 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.
– Bart van Ingen Schenau
Dec 24 '18 at 13:04
@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 '18 at 13:13
add a comment |
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.
answered Dec 24 '18 at 8:23
Martin Maat
8,03221131
"bits are so 20th century computerish": What do you mean by this?
– Giorgio
Dec 24 '18 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.
– Martin Maat
Dec 24 '18 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 '18 at 17:19
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?
– Martin Maat
Dec 24 '18 at 19:41
add a comment |
Your Answer
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "131"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fsoftwareengineering.stackexchange.com%2fquestions%2f384496%2fis-there-a-programming-language-where-every-string-is-a-valid-program%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
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?
edited Dec 30 '18 at 20:07
alecxe
18114
answered Dec 24 '18 at 8:06
Philip Kendall
6,31321926
1
"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 '18 at 10:26
1
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 '18 at 11:47
add a comment |
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?
edited Dec 30 '18 at 20:07
alecxe
18114
answered Dec 24 '18 at 8:06
Philip Kendall
6,31321926
1
"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 '18 at 10:26
1
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 '18 at 11:47
add a comment |
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?
edited Dec 30 '18 at 20:07
alecxe
18114
answered Dec 24 '18 at 8:06
Philip Kendall
6,31321926
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?
edited Dec 30 '18 at 20:07
alecxe
18114
answered Dec 24 '18 at 8:06
Philip Kendall
6,31321926
edited Dec 30 '18 at 20:07
alecxe
18114
edited Dec 30 '18 at 20:07
alecxe
18114
edited Dec 30 '18 at 20:07
alecxe
18114
18114
answered Dec 24 '18 at 8:06
Philip Kendall
6,31321926
answered Dec 24 '18 at 8:06
Philip Kendall
6,31321926
answered Dec 24 '18 at 8:06
Philip Kendall
6,31321926
6,31321926
1
"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 '18 at 10:26
1
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 '18 at 11:47
add a comment |
1
"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 '18 at 10:26
1
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 '18 at 11:47
1
1
"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 '18 at 10:26
"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 '18 at 10:26
1
1
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 '18 at 11:47
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 '18 at 11:47
add a comment |
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.
answered Dec 24 '18 at 7:57
Bart van Ingen Schenau
49.4k979127
4
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.
– Jörg W Mittag
Dec 24 '18 at 9:00
1
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 '18 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.
– Bart van Ingen Schenau
Dec 24 '18 at 13:04
@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 '18 at 13:13
add a comment |
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.
answered Dec 24 '18 at 7:57
Bart van Ingen Schenau
49.4k979127
4
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.
– Jörg W Mittag
Dec 24 '18 at 9:00
1
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 '18 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.
– Bart van Ingen Schenau
Dec 24 '18 at 13:04
@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 '18 at 13:13
add a comment |
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.
answered Dec 24 '18 at 7:57
Bart van Ingen Schenau
49.4k979127
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.
answered Dec 24 '18 at 7:57
Bart van Ingen Schenau
49.4k979127
answered Dec 24 '18 at 7:57
Bart van Ingen Schenau
49.4k979127
answered Dec 24 '18 at 7:57
Bart van Ingen Schenau
49.4k979127
answered Dec 24 '18 at 7:57
Bart van Ingen Schenau
49.4k979127
49.4k979127
4
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.
– Jörg W Mittag
Dec 24 '18 at 9:00
1
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 '18 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.
– Bart van Ingen Schenau
Dec 24 '18 at 13:04
@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 '18 at 13:13
add a comment |
4
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.
– Jörg W Mittag
Dec 24 '18 at 9:00
1
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 '18 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.
– Bart van Ingen Schenau
Dec 24 '18 at 13:04
@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 '18 at 13:13
4
4
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.
– Jörg W Mittag
Dec 24 '18 at 9:00
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.
– Jörg W Mittag
Dec 24 '18 at 9:00
1
1
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 '18 at 10:47
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 '18 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.
– Bart van Ingen Schenau
Dec 24 '18 at 13:04
@docbrown, in the examples I do see sequences of [Space][Tab], so I am not sure where you got your conclusion from.
– Bart van Ingen Schenau
Dec 24 '18 at 13:04
@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 '18 at 13:13
@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 '18 at 13:13
add a comment |
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.
answered Dec 24 '18 at 8:23
Martin Maat
8,03221131
"bits are so 20th century computerish": What do you mean by this?
– Giorgio
Dec 24 '18 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.
– Martin Maat
Dec 24 '18 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 '18 at 17:19
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?
– Martin Maat
Dec 24 '18 at 19:41
add a comment |
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.
answered Dec 24 '18 at 8:23
Martin Maat
8,03221131
"bits are so 20th century computerish": What do you mean by this?
– Giorgio
Dec 24 '18 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.
– Martin Maat
Dec 24 '18 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 '18 at 17:19
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?
– Martin Maat
Dec 24 '18 at 19:41
add a comment |
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.
answered Dec 24 '18 at 8:23
Martin Maat
8,03221131
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.
answered Dec 24 '18 at 8:23
Martin Maat
8,03221131
answered Dec 24 '18 at 8:23
Martin Maat
8,03221131
answered Dec 24 '18 at 8:23
Martin Maat
8,03221131
answered Dec 24 '18 at 8:23
Martin Maat
8,03221131
8,03221131
"bits are so 20th century computerish": What do you mean by this?
– Giorgio
Dec 24 '18 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.
– Martin Maat
Dec 24 '18 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 '18 at 17:19
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?
– Martin Maat
Dec 24 '18 at 19:41
add a comment |
"bits are so 20th century computerish": What do you mean by this?
– Giorgio
Dec 24 '18 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.
– Martin Maat
Dec 24 '18 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 '18 at 17:19
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?
– Martin Maat
Dec 24 '18 at 19:41
"bits are so 20th century computerish": What do you mean by this?
– Giorgio
Dec 24 '18 at 12:51
"bits are so 20th century computerish": What do you mean by this?
– Giorgio
Dec 24 '18 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.
– Martin Maat
Dec 24 '18 at 13:50
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.
– Martin Maat
Dec 24 '18 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 '18 at 17:19
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 '18 at 17:19
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?
– Martin Maat
Dec 24 '18 at 19:41
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?
– Martin Maat
Dec 24 '18 at 19:41
add a comment |
Thanks for contributing an answer to Software Engineering Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fsoftwareengineering.stackexchange.com%2fquestions%2f384496%2fis-there-a-programming-language-where-every-string-is-a-valid-program%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
@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 '18 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 '18 at 7:24
@Neil: that is not a Turing-complete language.
– Doc Brown
Dec 24 '18 at 10:35