能否用指定四个有限函数实现decrement函数？若可行如何实现？

Absolutely! You can implement the dec(x) function (which decrements x by 1) using only increment(x), assign(x,y), zero(x), and loop(x). Here's how to do it, along with a breakdown of the logic:

Step-by-Step Implementation #

First, we'll need a temporary variable to track intermediate values (let's call it tmp). Here's the full implementation using only the allowed primitives:

function dec(x) {
  let tmp;
  zero(tmp); // Initialize temporary variable to 0
  loop(x) {
    assign(x, tmp); // Set x to the current value of tmp
    increment(tmp); // Increase tmp by 1
  }
}

How It Works #

Let's walk through the logic with a concrete example to make it clear. Suppose x starts at 4:

1. We first set tmp to 0 using zero(tmp).
2. The loop(x) runs 4 times (since x is 4 initially):
   • First iteration: assign(x, tmp) sets x to 0; increment(tmp) makes tmp 1.
   • Second iteration: assign(x, tmp) sets x to 1; increment(tmp) makes tmp 2.
   • Third iteration: assign(x, tmp) sets x to 2; increment(tmp) makes tmp 3.
   • Fourth iteration: assign(x, tmp) sets x to 3; increment(tmp) makes tmp 4.
3. After the loop finishes, x is 3—exactly the result of x--!

Key Insight #

Instead of trying to "subtract 1" directly (which we can't do with the given primitives), we use the loop to build up tmp incrementally, while updating x to stay one step behind tmp. By the time we've looped x times, x ends up being the original value minus 1.

Edge Case Note #

This works for all non-negative integer values of x:

• If x is 0, the loop won't run at all, and x stays 0 (which matches the behavior of x-- in many languages when x starts at 0, avoiding underflow).

内容的提问来源于stack exchange，提问作者Ozymandias