Skip to main content
added 5 characters in body
Source Link
orlp
  • 13.9k
  • 1
  • 26
  • 41

is EVEN undecidable? How can you prove its undecidability?

It depends entirely on the enumeration that you use. E.g. one could make an enumeration that maps all Turing machines that halt with 1000 steps to an even index and all others to odd indices. Then EVEN is still an infinite set but decidable.

However a simple way to prove EVEN undecidable (assuming your enumeration is anything sane) is to show that for every Turing machine T there exists a machine T' that has an even index but identical behavior. You can do this by adding unreachable states, or useless extra transitions, etc, as long as it switches the parity of the enumeration.

What about other infinite subsets of TMs (for which we ask whether they halt on an empty input tape)? Would this problem still be undecidable or does that depend on the subset?

Entirely depends on the subset. See the example above, "the set of all Turing machines that halt within 1000 steps" is infinite, and trivially decidable. Other examples could include any mapping from infinite families of functions that you know that halt to Turing machines. All you need is an ontoinjective mapping - you don't need to decide behavioral equivalence.

is EVEN undecidable? How can you prove its undecidability?

It depends entirely on the enumeration that you use. E.g. one could make an enumeration that maps all Turing machines that halt with 1000 steps to an even index and all others to odd indices. Then EVEN is still an infinite set but decidable.

However a simple way to prove EVEN undecidable (assuming your enumeration is anything sane) is to show that for every Turing machine T there exists a machine T' that has an even index but identical behavior. You can do this by adding unreachable states, or useless extra transitions, etc, as long as it switches the parity of the enumeration.

What about other infinite subsets of TMs (for which we ask whether they halt on an empty input tape)? Would this problem still be undecidable or does that depend on the subset?

Entirely depends on the subset. See the example above, "the set of all Turing machines that halt within 1000 steps" is infinite, and trivially decidable. Other examples could include any mapping from infinite families of functions that you know that halt to Turing machines. All you need is an onto mapping - you don't need to decide behavioral equivalence.

is EVEN undecidable? How can you prove its undecidability?

It depends entirely on the enumeration that you use. E.g. one could make an enumeration that maps all Turing machines that halt with 1000 steps to an even index and all others to odd indices. Then EVEN is still an infinite set but decidable.

However a simple way to prove EVEN undecidable (assuming your enumeration is anything sane) is to show that for every Turing machine T there exists a machine T' that has an even index but identical behavior. You can do this by adding unreachable states, or useless extra transitions, etc, as long as it switches the parity of the enumeration.

What about other infinite subsets of TMs (for which we ask whether they halt on an empty input tape)? Would this problem still be undecidable or does that depend on the subset?

Entirely depends on the subset. See the example above, "the set of all Turing machines that halt within 1000 steps" is infinite, and trivially decidable. Other examples could include any mapping from infinite families of functions that you know that halt to Turing machines. All you need is an injective mapping - you don't need to decide behavioral equivalence.

Source Link
orlp
  • 13.9k
  • 1
  • 26
  • 41

is EVEN undecidable? How can you prove its undecidability?

It depends entirely on the enumeration that you use. E.g. one could make an enumeration that maps all Turing machines that halt with 1000 steps to an even index and all others to odd indices. Then EVEN is still an infinite set but decidable.

However a simple way to prove EVEN undecidable (assuming your enumeration is anything sane) is to show that for every Turing machine T there exists a machine T' that has an even index but identical behavior. You can do this by adding unreachable states, or useless extra transitions, etc, as long as it switches the parity of the enumeration.

What about other infinite subsets of TMs (for which we ask whether they halt on an empty input tape)? Would this problem still be undecidable or does that depend on the subset?

Entirely depends on the subset. See the example above, "the set of all Turing machines that halt within 1000 steps" is infinite, and trivially decidable. Other examples could include any mapping from infinite families of functions that you know that halt to Turing machines. All you need is an onto mapping - you don't need to decide behavioral equivalence.