Questions tagged [theory-of-computation]

For questions related to the theory of computation in the context of artificial intelligence.

Filter by
Sorted by
Tagged with
1 vote
0 answers
27 views

Can teacher forcing in RNN ensure Turing completeness?

RNN has the same capability as a universal Turing machine. But I am confused whether RNN holds the same capabilities if we use teacher forcing. Consider the following excerpts from paragraphs taken ...
user avatar
  • 3,099
3 votes
1 answer
233 views

Does Rice's theorem prove safe AI is undecidable?

According to Wikipedia In computability theory, Rice's theorem states that all non-trivial, semantic properties of programs are undecidable. A semantic property is one about the program's ...
user avatar
2 votes
2 answers
353 views

Would an artificial general intelligence have to be Turing complete?

For the purposes of this question, let's suppose that an artificial general intelligence (AGI) is defined as a machine that can successfully perform any intellectual task that a human being can [1]. ...
user avatar
4 votes
3 answers
223 views

Shouldn't Gödel's incompleteness theorems disprove the physical symbol system hypothesis?

According to the Wikipedia page of the physical symbol system hypothesis (PSSH), this hypothesis seems to be a vividly debated topic in philosophy of AI. But, since it's about formal systems, shouldn'...
user avatar
  • 715
6 votes
1 answer
243 views

What does "hard for AI" look like?

In theoretical computer science, there is a massive categorization of the difficulty of various computational problems in terms of their asymptotic worst-time computational complexity. There doesn't ...
user avatar
14 votes
3 answers
1k views

What are some implications of Gödel's theorems on AI research?

Note: My experience with Gödel's theorem is quite limited: I have read Gödel Escher Bach; skimmed the 1st half of Introduction to Godel's Theorem (by Peter Smith); and some random stuff here and there ...
user avatar
19 votes
2 answers
2k views

What limits, if any, does the halting problem put on Artificial Intelligence?

Given the proven halting problem for Turing machines, can we infer limits on the ability of strong Artificial Intelligence?
user avatar
  • 2,313