在计算理论中易于说明的问题

Question

我正在寻找有趣且易于说明的可计算性问题（可以通过本科生在计算性方面的第一门课程可以理解），以提供开放问题的示例（显然我希望学生能够理解问题而无需太多新的问题定义，对它们也很有趣）。

我发现 此列表 但是，对于本科生来说，其中的问题似乎太复杂了，需要花费大量时间给出定义。到目前为止，我发现的唯一问题是

与理性数字相比，二芬太汀问题是否可以决定？

您知道在计算理论中是否知道其他有趣且易于说明的问题？

Answer 1

关于图灵学位的poset $（d， leq_t）$的一个著名的公开问题是它是否具有非平凡的自动形态。也就是说，是否存在非身份射击$ f colon d to d $，以使$ a leq_t b $ i时，并且仅当$ f（a） leq_t f（b）$？