Skip to main content
13 votes

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

The halting problem is an example of a general phenomenon known as Undecidability, which shows that there are problems no Turing machine can solve in finite time. Let's consider the generalization ...
Harsh's user avatar
  • 1,315
11 votes
Accepted

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

Does the halting problem imply any limits on human cognition? Yes, absolutely--that there are pieces of code a human could look at and not be sure whether or not it will halt in finite time. (...
Matthew Gray's user avatar
  • 4,272
7 votes
Accepted

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

Definitely there are a lot of implications for AI, including: Inference with first-order-logic is semi-decidable. This is a big disappointment for all the folks that wanted to use logic as a primary ...
randomsurfer_123's user avatar
5 votes
Accepted

What does "hard for AI" look like?

Nice Question! This is a perennial topic of discussion among AI researchers. The short answer is "we don't really know which topics are hard in general, but we do know which we haven't got good ...
John Doucette's user avatar
3 votes
Accepted

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

The PSSH is often attacked via either Godel's theorems or Turing's incomputability theorem. However, both attacks have an implicit assumption: that to be intelligent is to be able to decide ...
John Doucette's user avatar
2 votes

Would an artificial general intelligence have to be Turing complete?

A system is Turing complete if it can be used to simulate any Turing machine. Given the Church-Turing thesis (which has not yet been proven), a human brain can compute any function that a Turing ...
nbro's user avatar
  • 40.9k
2 votes

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

Although there seems to be an apt analogy between Gödel's theorems and the PSHH, there is nothing formal linking the two together. More concretely, Gödel's theorems are about systems that decide ...
k.c. sayz 'k.c sayz''s user avatar
1 vote

What kind of language in theory of computation language includes current LLMs?

You're right Turing machines are enough for current LLMs training and inference due to its recursively enumerable (RE) power regarding the generation of any valid strings of any computational language....
cinch's user avatar
  • 2,277
1 vote

Would an artificial general intelligence have to be Turing complete?

My answer is yes, but in a trivial way. The least you would expect from an intelligent agent is that it is able to execute a given Turing machine on a given input. This requires actually no ...
vdbuss's user avatar
  • 81
1 vote

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

I've written an extensive article on this some twenty years ago, which was published in Engineering Applications of Artificial Intelligence 12 (1999) 655-659. It's fairly technical and you can read it ...
cjbj's user avatar
  • 111
1 vote

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

I found this paper by mathematician and philosopher Solomon Feferman on Gödel's 1951 Gibbs lecture on certain philosophical consequences of the incompleteness theorems, while reading the following ...
nbro's user avatar
  • 40.9k

Only top scored, non community-wiki answers of a minimum length are eligible