AI-complete

To translate accurately, a machine must be able to understand the text. It must be able to follow the author's argument, so it must have some ability to reason. It must have extensive world knowledge so that it knows what is being discussed — it must at least be familiar with all the same commonsense facts that the average human translator knows. Some of this knowledge is in the form of facts that can be explicitly represented, but some knowledge is unconscious and closely tied to the human body: for example, the machine may need to understand how an ocean makes one feel to accurately translate a specific metaphor in the text. It must also model the authors' goals, intentions, and emotional states to accurately reproduce them in a new language. In short, the machine is required to have wide variety of human intellectual skills, including reason, commonsense knowledge and the intuitions that underlie motion and manipulation, perception, and social intelligence. Machine translation, therefore, is believed to be AI-complete: it may require strong AI to be done as well as humans can do it.

The complexity of solving the following problems with a human-assisted Turing machine is:[15]

• Optical character recognition for printed text: ${\displaystyle \langle O(1),poly(n)\rangle }$
• Turing test:
  • for an ${\displaystyle n}$-sentence conversation where the oracle remembers the conversation history (persistent oracle): ${\displaystyle \langle O(n),O(n)\rangle }$
  • for an ${\displaystyle n}$-sentence conversation where the conversation history must be retransmitted: ${\displaystyle \langle O(n),O(n^{2})\rangle }$
  • for an ${\displaystyle n}$-sentence conversation where the conversation history must be retransmitted and the person takes linear time to read the query: ${\displaystyle \langle O(n^{2}),O(n^{2})\rangle }$
• ESP game: ${\displaystyle \langle O(n),O(n)\rangle }$
• Image labelling (based on the Arthur–Merlin protocol): ${\displaystyle \langle O(n),O(n)\rangle }$
• Image classification: human only: ${\displaystyle \langle O(n),O(n)\rangle }$, and with less reliance on the human: ${\displaystyle \langle O(\log n),O(n\log n)\rangle }$.