Skip to main content
Theoretical Computer Science

Return to Answer

added 58 characters in body
Source Link
Marzio De Biasi
Marzio De Biasi
  • 23.2k
  • 2
  • 58
  • 128

Just an extended comment trying to interpret the question.

Given a Turing machine $M$ that is promised to halt halts on all input strings; $M$ is called incomprehensible if and only if for at least one positive semidefinite real number integer $r$ the following question decision problem $Q_{M,r}$ is undecidable (i.e. it is impossible to construct a single algorithm that always leads to a correct yes-or-no answer):

OPTION 1

$Q_{M,r}(n)$ = "Does $M$ halts in less than $n^r$ steps on all inputs of length $n$ ?"

Trivially decidable (finite $2^n$ strings and $M$ always halts by hypothesis) $\Rightarrow$ there are no incomprehensible TMs

OPTION 2

$Q_{M,r}$ = "Is $M$ running time $O(n^r)$ ?"

Trivially decidable (1 or 0) $\Rightarrow$ there are no incomprehensible TMs

And if you ask: "Ok, but can we calculate the value 1 or 0 to build the algorithm that answer the question of Option 2?", then we fall back to this:

$Q_{r}(M)$ = "Is $M$ running time $O(n^r)$?" which is undecidable (using the standard definition of undecidable) as showed by Emanuele. But in this version M is an input of the problem and not the fixed $M$ for which you are defining the notion of "incomprehensible".

Just an extended comment trying to interpret the question.

Given a Turing machine $M$ that is promised to halt halts on all input strings; $M$ is called incomprehensible if and only if for at least one positive semidefinite real number integer $r$ the following question decision problem $Q_{M,r}$ is undecidable (i.e. it is impossible to construct a single algorithm that always leads to a correct yes-or-no answer):

OPTION 1

$Q_{M,r}(n)$ = "Does $M$ halts in less than $n^r$ steps on all inputs of length $n$ ?"

Trivially decidable $\Rightarrow$ there are no incomprehensible TMs

OPTION 2

$Q_{M,r}$ = "Is $M$ running time $O(n^r)$ ?"

Trivially decidable (1 or 0) $\Rightarrow$ there are no incomprehensible TMs

And if you ask: "Ok, but can we calculate the value 1 or 0 to build the algorithm that answer the question of Option 2?", then we fall back to this:

$Q_{r}(M)$ = "Is $M$ running time $O(n^r)$?" which is undecidable (using the standard definition of undecidable) as showed by Emanuele. But in this version M is an input of the problem and not the fixed $M$ for which you are defining the notion of "incomprehensible".

Just an extended comment trying to interpret the question.

Given a Turing machine $M$ that is promised to halt halts on all input strings; $M$ is called incomprehensible if and only if for at least one positive semidefinite real number integer $r$ the following question decision problem $Q_{M,r}$ is undecidable (i.e. it is impossible to construct a single algorithm that always leads to a correct yes-or-no answer):

OPTION 1

$Q_{M,r}(n)$ = "Does $M$ halts in less than $n^r$ steps on all inputs of length $n$ ?"

Trivially decidable (finite $2^n$ strings and $M$ always halts by hypothesis) $\Rightarrow$ there are no incomprehensible TMs

OPTION 2

$Q_{M,r}$ = "Is $M$ running time $O(n^r)$ ?"

Trivially decidable (1 or 0) $\Rightarrow$ there are no incomprehensible TMs

And if you ask: "Ok, but can we calculate the value 1 or 0 to build the algorithm that answer the question of Option 2?", then we fall back to this:

$Q_{r}(M)$ = "Is $M$ running time $O(n^r)$?" which is undecidable (using the standard definition of undecidable) as showed by Emanuele. But in this version M is an input of the problem and not the fixed $M$ for which you are defining the notion of "incomprehensible".

Source Link
Marzio De Biasi
Marzio De Biasi
  • 23.2k
  • 2
  • 58
  • 128

Just an extended comment trying to interpret the question.

Given a Turing machine $M$ that is promised to halt halts on all input strings; $M$ is called incomprehensible if and only if for at least one positive semidefinite real number integer $r$ the following question decision problem $Q_{M,r}$ is undecidable (i.e. it is impossible to construct a single algorithm that always leads to a correct yes-or-no answer):

OPTION 1

$Q_{M,r}(n)$ = "Does $M$ halts in less than $n^r$ steps on all inputs of length $n$ ?"

Trivially decidable $\Rightarrow$ there are no incomprehensible TMs

OPTION 2

$Q_{M,r}$ = "Is $M$ running time $O(n^r)$ ?"

Trivially decidable (1 or 0) $\Rightarrow$ there are no incomprehensible TMs

And if you ask: "Ok, but can we calculate the value 1 or 0 to build the algorithm that answer the question of Option 2?", then we fall back to this:

$Q_{r}(M)$ = "Is $M$ running time $O(n^r)$?" which is undecidable (using the standard definition of undecidable) as showed by Emanuele. But in this version M is an input of the problem and not the fixed $M$ for which you are defining the notion of "incomprehensible".