Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Recursively enumerable language with infinite alphabet

  1. Nov 18, 2008 #1
    Is an infinite language with an infinite alphabet always recursively enumerable?
    Last edited: Nov 18, 2008
  2. jcsd
  3. Nov 18, 2008 #2
    isn't it just enumerable?
  4. Nov 19, 2008 #3
    What's "enumerable"?
  5. Nov 19, 2008 #4
    countablely infinate
  6. Nov 19, 2008 #5


    User Avatar
    Science Advisor
    Homework Helper

    Last edited: Nov 19, 2008
  7. Nov 19, 2008 #6
    So.... no? Interesting.
  8. Nov 19, 2008 #7


    User Avatar
    Staff Emeritus
    Science Advisor

    If the language has uncountable alphabet, surely not?
  9. Nov 20, 2008 #8
    I was thinking that since the alphabet is infinite (countable or not), a Turing machine would need infinitely many states to recognize it, which goes against the definition of a TM.
  10. Nov 20, 2008 #9
    Isn't everything, should you accept the axiom of choice? I guess you meant it in the constructable sense.
  11. Nov 21, 2008 #10
    What does the axiom of choice have to do with anything?
  12. Nov 21, 2008 #11
    Ah, my mistake. See, I was thinking in the lines of the well ordering theorem. But the theorem doesn't state anything about every element of set having a predecessor, so it doesn't necessarily equate denumerability. I knew this was weird.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?

Similar Discussions: Recursively enumerable language with infinite alphabet
  1. Integral: recursion (Replies: 12)

  2. Simple recursion (Replies: 3)

  3. On Real Enumeration (Replies: 20)