Is a 'discrete language' well-defined?
-
29-09-2020 - |
Question
Are the following well-defined formal languages (in these cases: subsets of {0,1}*) ?
An argument w is a member of L under the following rules...
Example1:
If more than half of w's digits are 1's --> it is a member of L iff it is a member of language A (fill in your favorite decidable A to complete example).
If more than half of w's digits are 0's --> it is a member of L iff it is a member of language B (fill in your favorite decidable B to complete example).
If exactly half of w's digits are 1's and half are 0's then w is not a member of L.
Example 2:
If w is longer than 10 bits it has to be a member of decidable language A to be a member of L
If w is 10 bits or less it has to be a member of decidable language B to be a member of L.
The general question: are the above type of languages (discrete) well-defined?
The same way a function can be discrete or continuous I am nicknaming these types of definitions 'discrete' definitions for languages because based on what type of input you are, your rule (reason) for membership/non-membership can be different from other arguments'. I would assume this is ok? There does exist an argument that all discrete functions are not computable (or that all computable functions are continuous), but I don't think this argument holds if all the inputs are of finite precision (as is the case with finite binary strings)
Solution
A language $L \subseteq \{0,1\}^*$ is well-defined if, for each possible word $w \in \{0,1\}^*$, it is clearly specified whether $w$ is in $L$ or not.
This means that your rules must cover every case (for every word $w \in \{0,1\}^*$, at least one of your rules specifies whether $w$ is in $L$ or not), and that there are no contradictions (there does not exist any word $w \in \{0,1\}^*$ where one rule says that $w$ is in $L$ and another rule says $w$ is not in $L$).
Yes, you can use case analysis to define a language, or to define anything else (a set, a function, etc.), so long as the cases cover every case and do not contradict each other. This is not a matter of computer science; it is a matter of mathematics.
For both of your examples, yes, if the languages $A,B$ have been defined, then your definition of $L$ is well-defined.
OTHER TIPS
There does exist an argument that all discrete functions are not computable (or that all computable functions are continuous), but I don't think this argument holds if all the inputs are of finite precision (as is the case with finite binary strings)
There is indeed a notion of Continuous functions which correspond 1:1 with Computable functions. They are Scott Continuous functions on certain Domains. Those are not related to your definition of 'discrete' functions (at least not that I can tell).