Skip to main content
added 95 characters in body
Source Link
Hernan_eche
  • 703
  • 1
  • 7
  • 23

Is there a need for $L\subseteq \Sigma^*$ to be infinite to be undecidable?

I mean what if we choose a language $L'$ be a bounded finite version of $L\subseteq \Sigma^*$, that is $|L'|\leq N$, ($N \in \mathbb{N}$), with $L' \subset L$. Is it possible for $L'$ to be an undecidable language?

I see that there is a problem of "How to choose the $N$ words that $\in$ $L' "$ for which we have to establish a rule for choosing which would be the first $N$ elements of $L'$, a kind of "finite" Kleene star operation. The aim is to find undecidability language without needing an infinite set, but I can't see it.

EDIT Note:

Although I chose an answer, many answers and all comments are important.

Is there a need for $L\subseteq \Sigma^*$ to be infinite to be undecidable?

I mean what if we choose a language $L'$ be a bounded finite version of $L\subseteq \Sigma^*$, that is $|L'|\leq N$, ($N \in \mathbb{N}$), with $L' \subset L$. Is it possible for $L'$ to be an undecidable language?

I see that there is a problem of "How to choose the $N$ words that $\in$ $L' "$ for which we have to establish a rule for choosing which would be the first $N$ elements of $L'$, a kind of "finite" Kleene star operation. The aim is to find undecidability language without needing an infinite set, but I can't see it.

Is there a need for $L\subseteq \Sigma^*$ to be infinite to be undecidable?

I mean what if we choose a language $L'$ be a bounded finite version of $L\subseteq \Sigma^*$, that is $|L'|\leq N$, ($N \in \mathbb{N}$), with $L' \subset L$. Is it possible for $L'$ to be an undecidable language?

I see that there is a problem of "How to choose the $N$ words that $\in$ $L' "$ for which we have to establish a rule for choosing which would be the first $N$ elements of $L'$, a kind of "finite" Kleene star operation. The aim is to find undecidability language without needing an infinite set, but I can't see it.

EDIT Note:

Although I chose an answer, many answers and all comments are important.

edited tags
Link
Kaveh
  • 22.5k
  • 4
  • 52
  • 112
Tweeted twitter.com/#!/StackCompSci/status/204984042817458176
deleted 4 characters in body
Source Link
Raphael
  • 72.9k
  • 30
  • 181
  • 393

Undecidability Language for a Is there an undecidable finite setlanguage of programs S, a finite $\mathcal{P}(S)$, and finite inputswords?

Knowing that there is no surjection from $S$ to $\mathcal{P}(S)$.

Is there a need for L$L\subseteq \Sigma^*$ to be infinite to be undecidable, i.e. $L\subseteq \Sigma^*$?

I mean what if we choose a language $L'$ be a bounded finite version of $L\subseteq \Sigma^*$,

  that is $|L'|\leq N$, ($N \in \mathbb{N}$), with $L' \subset L$ ,. Is it possible for $L'$ to be an undecidable language?

I see that there here is a problem of "How to choose the $N$ words that $\in$ $L' "$ for which we have to stablishestablish a rule for choosing which would be the first $N$ elements of $L'$, a kind of "finite" Kleene star operation..The The aim is to find undecidability language without needing an infinite set, but I can't see it.

Undecidability Language for a finite set of programs S, a finite $\mathcal{P}(S)$, and finite inputs?

Knowing that there is no surjection from $S$ to $\mathcal{P}(S)$.

Is there a need for L to be infinite to be undecidable, i.e. $L\subseteq \Sigma^*$?

I mean what if we choose a language $L'$ be a bounded finite version of $L\subseteq \Sigma^*$,

 $|L'|\leq N$, ($N \in \mathbb{N}$), with $L' \subset L$ , Is it possible for $L'$ to be an undecidable language?

I see there here is a problem of "How to choose the $N$ words that $\in$ $L' "$ for which we have to stablish a rule for choosing which would be the first $N$ elements of $L'$, a kind of "finite" Kleene star operation..The aim is to find undecidability language without needing an infinite set, but I can't see it.

Is there an undecidable finite language of finite words?

Is there a need for $L\subseteq \Sigma^*$ to be infinite to be undecidable?

I mean what if we choose a language $L'$ be a bounded finite version of $L\subseteq \Sigma^*$, that is $|L'|\leq N$, ($N \in \mathbb{N}$), with $L' \subset L$. Is it possible for $L'$ to be an undecidable language?

I see that there is a problem of "How to choose the $N$ words that $\in$ $L' "$ for which we have to establish a rule for choosing which would be the first $N$ elements of $L'$, a kind of "finite" Kleene star operation. The aim is to find undecidability language without needing an infinite set, but I can't see it.

deleted 37 characters in body
Source Link
Hernan_eche
  • 703
  • 1
  • 7
  • 23
Loading
deleted 37 characters in body
Source Link
Hernan_eche
  • 703
  • 1
  • 7
  • 23
Loading
edited title
Link
Hernan_eche
  • 703
  • 1
  • 7
  • 23
Loading
Source Link
Hernan_eche
  • 703
  • 1
  • 7
  • 23
Loading