<p>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.</p>

CC BY-SA 4.0
2024-03-05T15:24:13.427Z
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?
mti
CC BY-SA 4.0
2024-03-05T21:43:08.540Z
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.  https://blog.computationalcomplexity.org/2009/05/foundations-of-complexity.html
Lance Fortnow
CC BY-SA 4.0
2024-03-06T11:33:38.613Z
@mti: shortly it means that H_L is harder than L, because even with L as an oracle H_L is still undecidable.
Denis
CC BY-SA 4.0
2024-03-05T15:02:50.063Z
2024-03-05T15:02:50.063Z
Lance Fortnow
<p>I'm interested in understanding the complexity of languages.</p>
<p>If I wanted to construct a language that is very difficult to decide, how would I go about this?</p>
<p>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)</p>

CC BY-SA 4.0
2024-03-05T08:03:13.660Z
This is not a research-level question. Please repost it on https://cs.stackexchange.com and delete it here. But no, there is no hardest language.
Emil Jeřábek
CC BY-SA 4.0
2024-03-05T15:12:10.320Z
@EmilJeřábek Pleas help me understand: What constitutes a "research-level question"? Why is this not one of them?
mti
CC BY-SA 4.0
2024-03-05T15:32:12.380Z
@mti: There is a brief description of the scope of this site, and in particular what is meant by "research-level question" here: https://cstheory.stackexchange.com/help/on-topic.
Joshua Grochow
CC BY-SA 4.0
2024-03-05T15:35:12.327Z
@JoshuaGrochow OK, thx. I guess my question indeed does not qualify then. What a pity... I fear that there are not enough TCS people on cs.stackexchange.com to give me interesting and deep answers to my questions :D
mti
CC BY-SA 4.0
2024-03-05T15:42:11.700Z
To be honest, I am deeply unhappy that the TCS community on here seems so strict about this. TCS was one of my favorite topics in undergraduate studies. I admit, I haven't touched it in a while and am definitely not at "research-level" understanding of the field. But I am knowledgeable in related areas like applied cryptography and sometimes like to think about more fundamental TCS questions for a hobby. I think hobbyists can have interesting ideas as well and to just discard them feels a bit harsh.
mti
CC BY-SA 4.0
2024-03-05T16:04:12.347Z
Following up on that: I respect that the TCS community doesn't want to be flooded by stupid or uninteresting questions. I understand that this can harm the benefit of the whole community. Sadly, this seemingly leaves me without a place to ask questions like the above. I would like to discuss this in an appropriate place. Please see my post on meta TCS: https://cstheory.meta.stackexchange.com/questions/3109/what-is-research-level-question-again-no-place-for-beginners.
mti
CC BY-SA 4.0
2024-03-05T16:08:04.957Z
@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
Joshua Grochow
CC BY-SA 4.0
2024-03-05T18:34:47.677Z
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?
Solomon Slow
<cc.complexity-theory>
The most complex language?
mti
# The most complex language?

(Asked by: username_0 on 2024-03-04)

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)

**Tags:** cc.complexity-theory

> **Comments:**
> **username_1**: This is not a research-level question. Please repost it on https://cs.stackexchange.com and delete it here. But no, there is no hardest language.  
> **username_0**: @EmilJeřábek Pleas help me understand: What constitutes a "research-level question"? Why is this not one of them?  
> **username_2**: @username_0: There is a brief description of the scope of this site, and in particular what is meant by "research-level question" here: https://cstheory.stackexchange.com/help/on-topic.  
> **username_0**: @JoshuaGrochow OK, thx. I guess my question indeed does not qualify then. What a pity... I fear that there are not enough TCS people on cs.stackexchange.com to give me interesting and deep answers to my questions :D  
> **username_0**: To be honest, I am deeply unhappy that the TCS community on here seems so strict about this. TCS was one of my favorite topics in undergraduate studies. I admit, I haven't touched it in a while and am definitely not at "research-level" understanding of the field. But I am knowledgeable in related areas like applied cryptography and sometimes like to think about more fundamental TCS questions for a hobby. I think hobbyists can have interesting ideas as well and to just discard them feels a bit harsh.  
> **username_0**: Following up on that: I respect that the TCS community doesn't want to be flooded by stupid or uninteresting questions. I understand that this can harm the benefit of the whole community. Sadly, this seemingly leaves me without a place to ask questions like the above. I would like to discuss this in an appropriate place. Please see my post on meta TCS: https://cstheory.meta.stackexchange.com/questions/3109/what-is-research-level-question-again-no-place-for-beginners.  
> **username_2**: @username_0: 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  
> **username_3**: 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?  

---

## 1 answers

### Answer by username_4 on 2024-03-05. Score: 2 | Accepted answer

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.

> **Comments:**
> **username_0**: 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?  
> **username_4**: 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.  https://blog.computationalcomplexity.org/2009/05/foundations-of-complexity.html  
> **username_5**: @username_0: shortly it means that H_L is harder than L, because even with L as an oracle H_L is still undecidable.  

---

