質問

Let's say that an item is either a natural number or a list of items. Examples of items are:

  • 1
  • [2]
  • [4, [3, 1], 3, 4]

A rule states that two items are equal. For example:

  • 1 = 2
  • 3 = [3, 1]
  • [4, 3] = [1, 5]

When using these example rules, we can transform [4, [3, 2]] into [4, [3, 1]] into [4, 3] into [1, 5] and we can say that [4, [3, 2]] equals [1, 5].

I want to find an algorithm that, given items $a$ and $b$ and a finite set of rules, determines if $a = b$.

I already thought of an algorithm that works in some cases. But I hope to find an efficient algorithm that works in all cases. It would also be nice if the algorithm can detect $a \not= b$ instead of infinitely searching for ways to let $a = b$. Is this a known problem? Any help is appreciated.

Note: We can simplify the problem by only allowing the number 1 instead of every natural number. This is equivalent, because we can transform 1 into [1], 2 into [1, 1], 3 into [1, 1, 1], etcetera.

正しい解決策はありません

ライセンス: CC-BY-SA帰属
所属していません cs.stackexchange
scroll top