Recursively enumerable language with infinite alphabet

  • Context: Graduate 
  • Thread starter Thread starter Dragonfall
  • Start date Start date
  • Tags Tags
    Infinite Language
Click For Summary

Discussion Overview

The discussion revolves around the properties of infinite languages with infinite alphabets, specifically whether such languages are always recursively enumerable. Participants explore the implications of countability and the nature of Turing machines in this context.

Discussion Character

  • Debate/contested

Main Points Raised

  • One participant questions if an infinite language with an infinite alphabet is always recursively enumerable.
  • Another participant suggests that it might simply be enumerable.
  • A participant seeks clarification on the term "enumerable," defining it as countably infinite.
  • There is a suggestion that if the language has an uncountable alphabet, it cannot be recursively enumerable.
  • One participant argues that a Turing machine would require infinitely many states to recognize an infinite alphabet, which contradicts the definition of a Turing machine.
  • Another participant discusses the implications of the axiom of choice and its relation to countability, indicating a potential misunderstanding of the concepts involved.
  • A later reply reflects on the well-ordering theorem and its implications for denumerability, acknowledging confusion regarding the relationship between these concepts.

Areas of Agreement / Disagreement

Participants express differing views on the relationship between infinite languages, infinite alphabets, and recursive enumerability. There is no consensus on whether such languages are always recursively enumerable, and multiple competing views remain.

Contextual Notes

Participants reference concepts such as countability, the axiom of choice, and the well-ordering theorem, indicating that the discussion may involve nuanced definitions and assumptions that are not fully resolved.

Dragonfall
Messages
1,023
Reaction score
5
Is an infinite language with an infinite alphabet always recursively enumerable?
 
Last edited:
Mathematics news on Phys.org
isn't it just enumerable?
 
What's "enumerable"?
 
countablely infinate
 
So... no? Interesting.
 
If the language has uncountable alphabet, surely not?
 
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.
 
soandos said:
countablely infinite

Isn't everything, should you accept the axiom of choice? I guess you meant it in the constructable sense.
 
  • #10
What does the axiom of choice have to do with anything?
 
  • #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.
 

Similar threads

High School Are All Imaginable Integer Series Necessarily Infinite?
  • · Replies 17 ·
Replies
17
Views
2K
Graduate Is this Recursive Pattern in the Collatz Sequence Known?
  • · Replies 3 ·
Replies
3
Views
2K
Is this computability theory proof correct?
  • · Replies 1 ·
Replies
1
Views
2K
Turing-recognizable infinite language, decidable subset
  • · Replies 3 ·
Replies
3
Views
3K
Undergrad Is the Inverse Image of a Computable Function Recursively Enumerable?
  • · Replies 3 ·
Replies
3
Views
2K
High School Infinite universe, infinite volume from the beginning?
  • · Replies 22 ·
Replies
22
Views
2K
MHB Propositions for recursive functions
  • · Replies 18 ·
Replies
18
Views
4K
Undergrad Loophole in Godel's Incompleteness Theorem?
  • · Replies 24 ·
Replies
24
Views
4K
Graduate Generalized Diophantine equation and the method of infinite descent
  • · Replies 4 ·
Replies
4
Views
1K
Graduate Is this a valid physical analogy for the Riemann Hypothesis?
  • · Replies 5 ·
Replies
5
Views
2K