可计算性——图灵机可以计算输入的长度吗？

Question

我一直在寻找这个看似微不足道的问题的答案，但我没有找到任何答案。

Can a Turing machine, given a word w, calculate the length of the word?

Answer 1

是的，当然！这里有一些事情需要考虑：

• 你会如何设计一个 TM 来递增二进制数？
• 如何将其他 TM 用作子程序来计算输入长度？

另一个观点：请记住，根据 Church-Turing 论文，您可以使用任何有效的计算模型做任何事情，您也可以使用 TM 来做，因此由于其他模型可以测量输入长度，因此 TM 也可以做到。