We describe formal languages with their finite descriptions. For example we can describe a language simply by set-builder ( $\{ x : \phi(x)\}$) or we can describe something with its corresponding Turing machine.

If we consider a fixed property of languages, then we have class of languages that have this property. For example if there is a polynomial bounded DTM for a language, we say it is in class P.

It is natrual to ask, what complexity properties are decidable. There is a problem which may confused with my question. We can easily show that most properties of a Turing machine are undecidable. Take time property of a TM as instance. We can not say for a given TM halts within $f(n)$ steps for all input of length $n$. We can prove it by contradiction. Just Make a TM which with recursion theorem gets its own code, and use that decider to decide is it member of that specific class or not and do the oppossite to get contradiction.

But this complexity property is heavily depend on a specific description method which called TM. I guess, and not sure, that it is related somehow to Church-Turing thesis, but i am sure that the thesis talks about computability and not complexity property.

I guess there may be a simple “No” answer for my question, because its seems it is undecidable, but I can not clearify how and whenever I think about it ,Ibecame so confused. Because somehow I always fix a finite description method to describe a language and use that specific method to define a property. Sometimes I think maybe all complexity properties , like time, has to be defined with a specific model, or finite description, to be meaningful. Because it seems no sense when we consider time of solving a problem with no specific model of solving in our mind.

To be more specific, time property has no meaning when our finite description is FOL. In logic the length of a description and number of quantifiers of a description is matter (furmula that charecterize its members).

Another question is, if we fix Turing machine for complexity properties, can we say all complexity properties of languages are undecidable ?

Any related sources like books could be so helpful for me.


  • 1
    $\begingroup$ I've trouble understanding what exactly your question is. But yes asking about time complexity always requires some model of computation - how else could we measure how many computation steps we need. If you just care about Turing-Machines then all non-trivial properties are undecidable by Rice's theorem. If you use a non Turing-complete model of computation such as LOOP, some properties are decidable (e.g. all LOOP-programs halt). $\endgroup$
    – plshelp
    Mar 17, 2022 at 17:49


Your Answer

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