AI-повна задача

Для точного перекладу, машина повинна розуміти текст. Вона повинна відслідковувати хід думки автора, а отже, певним чином, вона має мислити. Машина повинна мати широкий спектр знань (а також здоровий глузд), щоб розуміти про що йде мова — вона, щонайменше, має бути ознайомлена зі всіма базовими фактами, що відомі пересічному перекладачу-людині. Хоч деякі знання можуть бути явно відображені в комп'ютері, інші є скоріш несвідомими і тісно пов'язаними з людським тілом: до прикладу, машина має зрозуміти, що ми відчуваємо, дивлячись на океан, щоб правильно перекласти відповідну метафору. Вона також повинна створити модель цілей, намірів, переживань та емоцій автора, щоб якомога краще передати їх засобами нової мови. Іншими словами, для якісного перекладу, машина має володіти рядом інтелектуальних здібностей, притаманних людині, зокрема мисленням, здоровим глуздом, а також інтуїтивними відчуттями, що лежать в основі рухів та маніпуляцій об'єктами, сприйняття, та соціальних навичок. Таким чином, машинний переклад вважається AI-повною задачею: вона вимагає від машини інтелекту майже людського рівня.

Складність розв'язання деяких відомих зачач за допомогою Машини Тюрінга з людиною-асистентом:[9]

• Оптичне розпізнавання символів друкованого тексту: ${\displaystyle \langle O(1),poly(n)\rangle }$
• Тест Тюрінга:
  • для послідовності з ${\displaystyle n}$ бесід, якщо суддя пам'ятає історію цих бесід (наполегливий суддя): ${\displaystyle \langle O(n),O(n)\rangle }$
  • для послідовності з ${\displaystyle n}$ бесід, якщо історія цих бесід має передаватись повторно: ${\displaystyle \langle O(n),O(n^{2})\rangle }$
  • для послідовності з ${\displaystyle n}$ бесід, якщо історія цих бесід має передаватись повторно, а для прочитання запиту потрібен лінійний час: ${\displaystyle \langle O(n^{2}),O(n^{2})\rangle }$
• ESP гра: ${\displaystyle \langle O(n),O(n)\rangle }$
• Маркування зображень (згідно з Протоколом Артура-Мерліна): ${\displaystyle \langle O(n),O(n)\rangle }$
• Категоризація зображень: лише людиною: ${\displaystyle \langle O(n),O(n)\rangle }$, з людською допомогою: ${\displaystyle \langle O(\log n),O(n\log n)\rangle }$.