1
$\begingroup$

I know that

  • decidable problem: has both counting (bijection with $\mathbb N $) and membership algorithm (TM halts for both member and non member strings )
  • semidecidable problem: has counting algorithm and TM halts for member strings
  • countable problem: has only counting algorithm

Now I have come across undecidable language set which does not have membership algorithm (as semi decidable languages at least have TM which halts for member strings, which is not the case for undecidable problems), that is it does have TM that halt neither for member string nor for non member string.

I have doubt about the relationship between these language classes.

I know "decidable $\subset$ semi decidable $\subset$ countable".

Where does "undecidable" fit here?

Is it like this?:

(Match the color of text with that of the border. Region color is lighter shades of corresponding enclosed texts.)

enter image description here

Q. Is above diagram correct? Also I want to add "countable" to above. I feel, for finite alphabet languages, countable will be proper superset of "undecidable". Is it right?

PS: I feel, earlier I based my understanding of "undecidable" on incorrect definition given in this question. So I draw wrong diagram earlier. I believe its correct now.

Improve this question
$\endgroup$
15
  • 1
    $\begingroup$ 1) "Undecidable" is just the complement of "decidable". Can you adjust your graphic using this? You may need colors. 2) "countable" in mathematics means only that there's a bijection with (a subset of) $\mathbb{N}$ -- it doesn't have to be computable! $\endgroup$
    – Raphael ♦
    Jan 22, 2019 at 19:28
  • 1
    $\begingroup$ I think your diagram is wrong, since it assumes that undecidable problems are always semi-decidable. Some semi-decidable problems are undecidable (like the Halting Problem) and all decidable problems are semi-decidable. $\endgroup$
    – Sagnik
    Jan 22, 2019 at 19:30
  • 1
    $\begingroup$ Also decidable problems aren't a subset of undecidable problems. The sets are complements of each other. $\endgroup$
    – Sagnik
    Jan 22, 2019 at 19:31
  • $\begingroup$ This is a good answer related to this topic: cs.stackexchange.com/questions/83815/… $\endgroup$
    – Sagnik
    Jan 22, 2019 at 19:33
  • 1
    $\begingroup$ I'm not sure what you mean by a "counting algorithm". To me, a counting algorithm is one that returns the number of elements of some set. That doesn't make much sense for infinite sets. Indeed, for most infinite sets, there isn't even any way of presenting that set as the input of an algorithm. $\endgroup$
    – David Richerby
    Jan 22, 2019 at 19:39

2 Answers 2

Reset to default
3
$\begingroup$

A language is defined as a set of strings over an alphabet. We will assume the usual situation where the alphabet is a finite set. Then the set of all strings are countably infinite. Why is it countable? Because we can list all strings of length 0, all strings of length 1, all strings of length 2, all strings of length 3 and so on.

The correct diagram should look like the following (where we assume P!= NP), where the enclosing unlabeled plane represents languages that are countable. Note all languages that sit outside of the region of "TM decidable" is "TM undecidable". Note that we usually say "decidable", "recognizable", "co-recognizable" and "undecidable" simply without the prefix "TM".

CS21 Decidability and Tractability Published by Shanna Hood https:\slideplayer\com-slide\5289813

For completeness, we have the following diagram that includes chomsky hierarchy.

CS 208 Computing Theory by Dr. Brahim Hnich https:\slideplayer.com\slide\8093532

Improve this answer
$\endgroup$
3
  • $\begingroup$ My confusion was primarily with decidable, recognizable, undecidable and countable languages. You have shown other possible language classes too. Q1. And I believe diagram that I have put in the question adheres with your diagrams. Right? Q2. How the scenario will be if the languages are of infinite alphabet? $\endgroup$
    – RajS
    Jan 23, 2019 at 14:33
  • 1
    $\begingroup$ Q1. I would say yes, assuming that "undecidable" in your diagram means all regions outside of region "decidable / co-decidable". $\endgroup$
    – John L.
    Jan 23, 2019 at 14:42
  • 1
    $\begingroup$ Q2. The case with infinite alphabet is an entirely different matter. Let a language over an infinite alphabet consists of an infinite subset of all strings of length one, i.e., the alphabet itself. Even for such a "simple" language, we may need to redefine Turing machine to allow infinite states so as to recognize it. That is why we rarely talk about infinite alphabet. There are huge (I mean, infinitely large) differences between finiteness and infinity. $\endgroup$
    – John L.
    Jan 23, 2019 at 14:48
3
$\begingroup$

Undecidable is simply the complement of decidable, as the name suggests: anything that is not decidable is undecidable. So the whole pink area of your diagram consists of undecidable languages.

All languages over finite alphabets are countable. For example, every string over alphabet $\{0,1\}$ is a natural number written in binary.1 Everything in your diagram is countable. We only ever consider finite alphabets; infinite alphabets aren't physically realizable because we can't store infinitely many distinguishable possibilities in a finite space.

1. A small problem is that $0$, $00$, $000$, etc. are all the number zero written in binary. So, instead, associate the binary string $xyz$ with the natural number $1xyz$ and now, every binary string represents a different natural number.

Improve this answer
$\endgroup$
4
  • $\begingroup$ hey David, I have updated the question along with the diagram three hours back. There is no pink color now in the diagram. I believe you mean to say that the whole square is now undecidable and countable? Also the whole square is "countable" only if we are talking about finite alphabet languages, right? (It wont be if we start talking about infinite alphabet languages.) $\endgroup$
    – RajS
    Jan 23, 2019 at 13:35
  • 2
    $\begingroup$ It's pink on my screen. And please don't edit your question in ways that invalidates answers. $\endgroup$
    – David Richerby
    Jan 23, 2019 at 13:39
  • $\begingroup$ Sorry I edited the question quite a lot, reflecting what I learnt after I first asked the question. But I edited it when there was no answer... $\endgroup$
    – RajS
    Jan 23, 2019 at 14:23
  • 2
    $\begingroup$ @anir OK, so your question hasn't changed since I posted my answer, and your diagram still contains a pink region. I'll add a few words about finiteness of alphabets. $\endgroup$
    – David Richerby
    Jan 23, 2019 at 14:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.