2

I'm very familiar with languages such as $L$={$a^n$ where $n$ is a prime number}. I know this language is decidable. However, I ran across a similar problem that asked if the set $X$ = {$p$ where $p$ is a prime number} is decidable or not. It probably is, but what exactly are they talking about when they say "set". How is it different from a language?

Thanks all.

pauliwago
  • 635

3 Answers3

1

One way to express this is that you code the natural numbers into a language, most often using unary or binary expansion, and ask whether the resulting language is decidable. So your example is exactly equivalent to asking whether the set of prime numbers is decidable, with the choice of a unary encoding. Happily, the encoding will not affect the answer to a problem of this kind, since Turing machines are perfectly happy to write unary notation into binary and vice-versa. The encoding does, however, become significant when questions of complexity come into play.

Kevin Carlson
  • 52,457
  • 4
  • 59
  • 113
1

A "set" is usually understood to be a collection of things that all share some common property, such as the set of all red fruits, the set of all animals that have kidneys, or the set of all numbers that are prime. A language is a set of strings, nothing more or less.

A number can be written as a numeral in any of several natural ways. For example, the number 135 might be written as 135, or in base 2 as 10000111, or in "unary" as 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111.

Such a string can be written onto the input tape of a Turing machine, and then you can run the machine and see if the machine accepts the input.

You can then ask the question of whether a particular set of numbers is decidable by asking the analogous question about the language consisting of the strings that represent those numbers. For example, is there a Turing machine that accepts the strings 0, 2, 4, …, 1788, … and rejects the strings 1, 3, 5, …, 1789, …? Yes, there is, and so we say that the set of even numbers is decidable.

In questions of decidability it does not matter whether we represent numbers with base-10 numerals, or base-2 numerals, or "unary" numerals, since a Turing machine can easily convert between these representations. So we allow ourself to forget about the strings that represent the numbers, and just focus on the numbers themselves. The language consisting of strings that represent even numbers is decidable, for any reasonable way of representing numbers as strings, so we just say that the set of even numbers is decidable, or we say that the property of evenness is decidable.

Your question is asking about the set of prime numbers. Is there a Turing machine which will accept the strings 2, 3, 5, 7, 11, 13, …, 1013,… and reject the others?

MJD
  • 65,394
  • 39
  • 298
  • 580
  • Yes there is, so it's decidable? Wouldn't the Turing Machine for this be identical to the Turing Machine with the language $a^n$ where $n$ is a prime number? (this can be accomplished with 2 tapes) – pauliwago Aug 13 '12 at 02:48
  • Yes there is, so it is decidable. But it is not identical to the Turing machine for accepting $a^p$, because the first Turing machine accepts the string 19 and the second does not, and the second one accepts the string aaaaaaaaaaaaaaaaaaa and the first does not. – MJD Aug 13 '12 at 02:51
  • Ohhh I see. We're talking about the number of a's being prime vs an ACTUAL prime number? – pauliwago Aug 13 '12 at 02:55
  • I understand now. Thank you very much, you are a lifesaver – pauliwago Aug 13 '12 at 02:56
  • One way to represent numbers is with base-10 numerals; you can build a Turing machine which will look at a 19 on the tape and say "yes" because it 19 prime, and look at an 18 on the tape and say "no" because 18 is not prime. You can also build a Turing machine which will look at an aaaaaaaaaaaaaaaaaaa on the tape and say "yes" because 19 is prime, and look at an aaaaaaaaaaaaaaaaaa on the tape and say "no" because 18 is not prime. Both can be done. It doesn't matter much which we do, so we tend to ignore the details of what is on the tape, and just ask if a TM can decide primality. – MJD Aug 13 '12 at 03:00
  • So the TM's CAN be identical, if we first choose to encode the string "7" to aaaaaaa before running it thru the TM? – pauliwago Aug 13 '12 at 03:05
  • 1
    I am distinguishing between the number 7, and its encoding as the string 7. The number 7 can also be encoded in many other ways, such as +007.00, or 1+(2×3), or aaaaaaa, depending on what is convenient. It is important in programming and CS to distinguish between a thing, such as the number 7, and its representation as a string, say as the string 7. A Turing machine which recognizes primes encoded as base-10 numerals is not identical to one which recognizes the set of strings ${{\tt a}^p | p \mbox{ is prime} }$, but we can think of them as doing the same thing. – MJD Aug 13 '12 at 03:09
  • The formalisation of this requirement that the objects in the set be strings is normally expressed as a language $L$ being a subset of $\Sigma^{\ast}$, where $\Sigma$ is an alphabet (i.e. a set of characters) and $^{\ast}$ is the Kleene star (operator). – Luke Mathieson Aug 13 '12 at 05:00
0

A language is a set, typically a set of strings or a set of natural numbers. Some models of computation, like Turing machines, take strings as inputs. Other models, like computer machines, take natural numbers as inputs. The difference is not really important, because there are very effective ways of representing a natural number as a string and very effective ways of representing a string as a natural number. The result is that, within computability, people use "language" and "set" more or less interchangeably. However, there is a connotation to "language" that is specific to computability; in set theory, they still talk about "sets" but not typically about "languages".

A similar example is that a "theory" in logic is just a set of formulas, so in that context they sometimes use "theory" and "set" interchangeably.

Carl Mummert
  • 81,604