1
$\begingroup$

I have come across the description of a function $F: \mathbb{N} \to \mathbb{N}$ where the function is defined one way for $n \in \mathcal{H}$ and another way for $n \notin \mathcal{H}.$ In this notation $\mathcal{H}$ is meant to denote the halting problem.

However, I am not sure what it means for an integer to be a member of the halting problem.

$\endgroup$
2
$\begingroup$

Turing machines can be encoded as integers in various ways. With respect to any such encoding, we define $\mathcal{H}$ as the set of integers $n$ such that the Turing machine encoded by $n$ halts on the empty input.

The encoding cannot be completely arbitrary. For example, you can design such an artificial encoding in which the parity of the encoding is its halting status. Instead, we fix some natural string encoding (closely following one of the many equivalent definitions of Turing machines), and convert it into an integer encoding $\alpha$ is one of several natural ways (for example, convert the string into a self-delimiting binary string, which can be interpreted as a natural number). We only consider encodings $\beta$ such that an encoding of type $\alpha$ can be converted into an encoding of type $\beta$ of an equivalent machine, and vice versa, in a computable way (by an algorithm). The difficulty of the halting problem (in terms of computability) is the same for all such encodings (which we could call admissible).

For more on the issue of admissibility, check out Wikipedia.

$\endgroup$
2
  • $\begingroup$ I've read that the halting problem is the problem of deciding whether a given Turing machine and input will halt for any TM and input pair. It seems if we fixed the TM, for certain cases we could of course decide the halting problem. However, is it the case that if we fix the input (as in your definition where it is fixed to be empty) that the problem is still undecidable for all TMs? If so, isn't the definition of the halting problem across all TM-input pairs too strong? $\endgroup$
    – Altitude5
    Sep 23 at 10:01
  • $\begingroup$ There are several variants of the halting problem. They are all equivalent from the point of view of computability. In particular, the problem of determining whether a given Turing machine halts on the empty input is undecidable. $\endgroup$ Sep 23 at 15:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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