nlp - 是否可以构建一个对给定 API 进行编程的图灵机？

Question

我想知道，是否可以定义一个 API 并将其作为TM图灵机的输入，输出将是代码c或任何其他自然/编程语言？

我猜不是，但我如何通过减少等正式显示它？

Answer 1

您的问题似乎是在询问是否可以编写一个程序（换句话说，图灵机），该程序接受程序规范（您称之为“API”）并以某种编程语言输出程序。答案是“当然”。让我们看几个例子。

1. 假设我将输入规范编写为 C 程序，并且我想用 C 输出程序。我将此图灵机程序称为“副本”，我可以用任何语言轻松实现它（或使用cp命令行上的命令）。

2. 假设我将输入规范编写为 C 程序，并且我想以汇编代码输出程序。我称这个图灵机程序为“编译器”，我可以用任何语言实现它（或者你可以下载一个已经存在的 C 编译器）。

3. 假设我用英语编写输入规范，我想用 C 语言输出一个程序。我称这个图灵机程序为“软件工程师”，我通过将这个人送到学校（或者你可以雇用现有的软件工程师）。

这里的寓意是，图灵机可以做任何人类可以做的事情（人类可以做任何图灵机可以做的事情）。但是，编写一个与人类一样通用的计算机程序真的非常非常困难。