-3
$\begingroup$

I'm interested in understanding the complexity of languages.

If I wanted to construct a language that is very difficult to decide, how would I go about this?

Is it known whether we can artificially construct a language that is the hardest language to decide? (or at least as hard as any other language)

$\endgroup$
8
  • 3
    $\begingroup$ This is not a research-level question. Please repost it on cs.stackexchange.com and delete it here. But no, there is no hardest language. $\endgroup$ Mar 5 at 8:03
  • $\begingroup$ @EmilJeřábek Pleas help me understand: What constitutes a "research-level question"? Why is this not one of them? $\endgroup$
    – mti
    Mar 5 at 15:12
  • 2
    $\begingroup$ @mti: There is a brief description of the scope of this site, and in particular what is meant by "research-level question" here: cstheory.stackexchange.com/help/on-topic. $\endgroup$ Mar 5 at 15:32
  • 4
    $\begingroup$ @mti: Many of the people that answer questions here also answer questions there! We may be a small community compared to AI/ML, but it's still large enough that there should be plenty there. Lots of questions in this vein do show up on cs.stackexchange - check out how many Qs they have under the tags "algorithms", "complexity-theory", "computability". I think maybe you are shortchanging the other site $\endgroup$ Mar 5 at 16:08
  • 1
    $\begingroup$ If a machine can decide whether or not a given string belongs to your language, then it should be possible to design a Turing machine that can decide it. Seems like your question is equivalent to asking, what is the most complex Turing machine that can be constructed? I'm just an amateur here, but it seems like that is equivalent to asking, what is the greatest number of arcs and nodes that any directed graph could possibly have? $\endgroup$ Mar 5 at 18:34

1 Answer 1

2
$\begingroup$

To be precise, for any language L, the halting problem relative to L is undecidable in L. So no hardest language, in the same sense that there is no largest number.

$\endgroup$
3
  • $\begingroup$ Unfortunately, I don't understand the implication "the halting problem relative to any language L is undecidable in L => there is no hardest language". Could you elaborate? And on the motivating question behind that, do we have any tools for constructing provably hard languages? $\endgroup$
    – mti
    Mar 5 at 15:24
  • 2
    $\begingroup$ Let me point to my Foundations of Complexity posts, particularly the first 6 to understand about the halting problem and how to construct provably hard languages. blog.computationalcomplexity.org/2009/05/… $\endgroup$ Mar 5 at 21:43
  • 1
    $\begingroup$ @mti: shortly it means that H_L is harder than L, because even with L as an oracle H_L is still undecidable. $\endgroup$
    – Denis
    Mar 6 at 11:33

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