0
$\begingroup$

I am working through the exercises in the book "Term Rewriting and All That" and got stuck on question 2.3. The question reads: find a reduction $\rightarrow$ on $\mathbb{N}$ such that $\rightarrow$ is decidable, but it is undecidable for some $n$ in normal form. A friend and I came up with two different solutions. But we both feel like these answers might not be correct and that there is a simpler solution that we are not seeing.

Our solutions:

First solution: Let relation $m \rightarrow n$ be any an $n$ such that $m$ is divisible by $n$. Let the normal form be 0. This seems to work because dividing by zero is undefined. Thus, the relation is decidable until we use the normal form 0. Second solution: We transform $x$ to be a program in some way and let $y$ be the number of steps. Then we define the relation $x \rightarrow y$, in which program $x$ halts after $y$ steps. Let the normal form be any program that does not halt. This seems to work because if the program does halt, we can always check if the relation holds. If the program does not halt, it becomes undecidable.

I am not sure if I understand it enough to provide an eloquent question, but I think my confusion boils down to this: In the context of abstract reduction systems. When is a relation decidable? And if a relation is decidable, how can it then also be undecidable at the same time for specific values? Does that not make it undecidable?

$\endgroup$
3
  • $\begingroup$ Okay, I tried to rewrite the question a bit. Please let me know if it's still not following the guidelines! $\endgroup$ Dec 10, 2023 at 13:33
  • $\begingroup$ Good edit,t his looks helpful! What does "undecidable for some n in normal form" mean? Do you know what that phrasing means? Is that the exact phrasing from the book? If you don't know what it means, then it is premature to try to solve the problem or to ask others to solve it, and you should instead ask what that phrase means, and provide sufficient context for us to understand it. Before one can solve a problem, one must first understand what the problem/goal is. $\endgroup$
    – D.W.
    Dec 10, 2023 at 23:59
  • $\begingroup$ Sure! The phrase itself is lifted verbatim from the exercise in the book. So this is all that is written about it. The normal form is defined in the book as follows: $x$ is in normal form (irreducible) iff it is not reducible. And: $y$ is a normal form of $x$ iff $x \rightarrow^{*} y$ and y is in normal form. The symbol $\rightarrow^{*}$ is a reflexive transitive symmetric closure. $\endgroup$ Dec 11, 2023 at 15:17

1 Answer 1

2
$\begingroup$

I don't know what is the definition for a reduction to be decidable. I would expect it is one of the following two:

Defn 1: $\to$ is decidable iff there is an algorithm $A$ that always halts and, on input $x$, either outputs some $y$ such that $x \to y$; or, if no such $y$ exists, outputs $\bot$.

Defn 2: $\to$ is decidable if there is an algorithm $A$ that always halts and, on input $x,y$, outputs whether $x \to y$ or not.

But I would hope that the book provides a definition or some context to help specify this.

I don't know what "undecidable for some $n$ in normal form" means. I cannot reconstruct any definition that is meaningful and non-trivial. My first attempts to guess at that meaning are as follows:

Defn 3: We say $\to$ is "undecidable for some $n$ in normal form" if there exists some $n \in \mathbb{N}$ such that $n$ is in normal form (i.e., $\not\exists y . n \to y$) and there is no algorithm $A$ that always halts and, on input $n$, either outputs some $y$ such that $n \to y$; or, if no such $y$ exists, outputs $\bot$.

Defn 4: We say $\to$ is "undecidable for some $n$ in normal form" if there exists some $n \in \mathbb{N}$ such that $n$ is in normal form (i.e., $\not\exists y . n \to y$) and there is no algorithm $A$ that always halts and, on input $y$, outputs whether $n \to y$ or not.

However, neither of these seem reasonable to me. Defn 3 is trivial (there is always such an algorithm, namely, the algorithm that always outputs $\bot$, so there does not exist any relation that satisfies Defn 3). Also, Defn 4 is also trivial (there is always such an algorithm, namely, the algorithm that always outputs "yes", so there does not exist any relation that satisfies Defn 4). So I cannot figure out the intended meaning of the exercise.

Until you understand the meaning of what is to be proven, it is premature to ask whether any particular solution is valid. First, I suggest you understand what are the criteria for a proposed solution to be considered valid. That might require reading more context in the book to see what you can figure out and what definitions it presents that might be relevant.

$\endgroup$
2
  • $\begingroup$ I feel like the question is formulated too vaguely in the book, or at least missing some definitions about decidability on abstract relation systems. I've reread the previous chapters to see if they mention decidability. It is only mentioned twice, once about identity, and once about joinability, never about abstract reduction relations in general: "Provided normal forms are computable and identity is decidable, equivalence also becomes decidable." and "Of course the test for joinability can be difficult (and even undecidable) if the relation does not terminate..." $\endgroup$ Dec 20, 2023 at 14:03
  • $\begingroup$ @RubenHensen, got it. Hopefully someone else with more expertise will be able to help, as I've exhausted my knowledge. Sorry. $\endgroup$
    – D.W.
    Dec 20, 2023 at 18:05

Your Answer

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

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