Recursively enumerable language with infinite alphabet

[Dragonfall]

Is an infinite language with an infinite alphabet always recursively enumerable?

 

[soandos]

isn't it just enumerable?

 

[Dragonfall]

What's "enumerable"?

 

[soandos]

countablely infinate

 

[CRGreathouse]

Is an infinite language with an infinite alphabet always recursively enumerable?

http://en.wikipedia.org/wiki/Productive_set

 

[Dragonfall]

So... no? Interesting.

 

[HallsofIvy]

If the language has uncountable alphabet, surely not?

 

[Dragonfall]

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.

 

[Werg22]

countablely infinite

Isn't everything, should you accept the axiom of choice? I guess you meant it in the constructable sense.

 

[Dragonfall]

What does the axiom of choice have to do with anything?

 

[Werg22]

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.