Skip to main content
18 votes
Accepted

Water Jug Problem in AI

Recoverable, as we can pour all water back to the 12L jug to restore the original state, hence any state derived thereof (by following the same steps from the start). The problem is, also, solvable: <...
OverLordGoldDragon's user avatar
10 votes

In what ways can we distinguish between a human and bot behavior?

The most common/obvious way is a challenge-response test that is easy for humans but hard for computers (of course, but not only, CAPTCHA). This kind of test is very effective{1} but falls under the ...
manlio's user avatar
  • 2,062
8 votes

Does the the undecidability of the Halting Problem eliminate the possibility of 'Hard AI'?

You're understanding of "solve all instances of the Halting Problem" is flawed. All instances means ALL instances. Every single one, ever. For example, no human knows if a Turing Machine verifying ...
Joey Eremondi's user avatar
8 votes
Accepted

How to determine the time and memory complexity for solving a sliding-tile puzzle?

The complexity of the BFS and DFS algorithms depend heavily on the graph being analyzed, and the search strategy being used. If we have a method to consistently get "closer" to a solution, ...
Exalted Toast's user avatar
7 votes

Google DeepDream Elaborated

The idea of DeepDream is this: pick some layer from the network (usually a convolutional layer), pass the starting image through the network to extract features at the chosen layer, set the gradient ...
Maxim's user avatar
  • 640
7 votes
Accepted

Bidirectional Dijkstra vs Dijkstra

Absolutely yes! your arguments are correct. And, as matter of fact, it is very easy to come up with a graph where Bidirectional Dijkstra would expand more nodes than Unidirectional Dijkstra, following ...
Carlos Linares López's user avatar
7 votes

What's the input to the decoder in a sequence to sequence autoencoder?

I was wondering the same and just stumbled across a nice tutorial by Quoc V. Le. The following explanation deals with the conditional case since this seems to be the common case. My explanation is ...
jns's user avatar
  • 171
7 votes
Accepted

Why do we use the log in gradient-based reinforcement algorithms?

We often take the logarithm because: Maximizing $\log \Phi(x)$ is equivalent to maximizing $\Phi(x)$, so in maximum-likelihood problems, we can maximize the log of the likelihood instead of ...
D.W.'s user avatar
  • 161k
7 votes

Water Jug Problem in AI

I couldn't in a quick Google through the textbooks tell whether recoverability requires immediate, single-move recoverability (ctrl-Z-style) with each undo step being O(1) complexity, and which can be ...
Dewi Morgan's user avatar
6 votes
Accepted

How do neural networks create results like its inputs?

These are known as Autoencoders. As you said, these neural networks are trained to produce output that is similar to the input, rather than output a classification of some kind. Internally, they do ...
Wil's user avatar
  • 368
6 votes

Is the halting problem claim true with the advent of AI

Even if we can design better AI solving problems we did not think possible even 10 years ago, they will always be computer programs. And as you said it yourself, "Alan Turing states that, there can't ...
holf's user avatar
  • 956
6 votes

How does machine learning relate to artificial intelligence?

Machine Learning is a subset of (the scientific field of) Artificial Intelligence. What is ML? Machine Learning is defined by Tom Mitchel: A computer program is said to learn from experience E ...
Martin Thoma's user avatar
  • 2,360
6 votes

Artificial intelligence and undecidibility

No. The Post correspondence problem is undecidable. That means that no computer program can solve it (in all cases). "Artificial intelligence" is just a computer program. Actually, "artificial ...
D.W.'s user avatar
  • 161k
6 votes
Accepted

Is Artificial General Intelligence possible with our current machine learning models?

The short answer is, we don't know! This is an open question in AI research. We know how neurons transmit signals, and can simulate that in a straightforward way: that's how layered perceptron models ...
Draconis's user avatar
  • 7,148
6 votes

Water Jug Problem in AI

Suppose the leftmost jug had 3 liters, the center jug had 2 liters, the right jug is empty. Suppose you poured the leftmost jug to the center jug. Now the leftmost jug is empty, and the center jug ...
Yuval Filmus's user avatar
5 votes
Accepted

What is the difference between Cased-based Reasoning and Rule-based reasoning?

As said in the comments, there may be a part of subjectivity in the answers to this question. Yet, I think it is fair to say that case-based reasoning mostly belongs to what is often called ...
Seb Destercke's user avatar
5 votes
Accepted

Turing tests and humans

The basic objective of a Turing test is to come up with such an intelligent machine, which actually mimics the human way of communicating. For that purpose, we'll carefully need to think about what ...
Syed Ali Hamza's user avatar
5 votes

How are artificial intelligence and Natural intelligence compared?

You are probably referring to ConceptNet (created by the Massachusetts Institute of Technology under its Artificial Intelligence program). It's a software system / semantic network containing lots of ...
manlio's user avatar
  • 2,062
5 votes

Does the the undecidability of the Halting Problem eliminate the possibility of 'Hard AI'?

Here's a thought experiment: the mathematical framework with which we usually work is called ZFC, and it has 9 axioms. Given a program $M$ and input $x$, a Turing Machine could iterate over all proofs ...
Lieuwe Vinkhuijzen's user avatar
5 votes

Prove consistency of maximum of two consistent heuristic functions?

Proof (Show consistency property of $h_3$): $$ h_3(n) = \max(h_1(n), h_2(n)) \\ \leq max(h_1(n')+c(n,a,n'), \ h_2(n')+c(n,a,n')) \\ \leq \max(h_1(n'), \ h_2(n')) + c(n,a,n') = h_3(n') + c(n,a,n') $$...
dtt's user avatar
  • 558
5 votes
Accepted

Explanation of proof of why connectedness is not conjunctively local of any order $k$

The predicate $\varphi_0$ depends on at most $k$ points. There are $k+1$ middle squares. So $\varphi_0$ cannot depend on all of them. That is, there is a middle square that $\varphi_0$ does not depend ...
Yuval Filmus's user avatar
5 votes
Accepted

How did the Logic Theorist prove the Pons Asinorum?

If you google "logic theorist source code" you find this which is clearly not the original source code, but presumably is a modernization of the ideas in the code. You can also find this 1963 RAND ...
Derek Elkins left SE's user avatar
5 votes

Being stuck and frustrated with my masters project

I have been implementing a branch and bound solver with heuristics for an NP-hard problem. It got complicated at some points and had to reimplement parts a couple of times. The problem was (I think), ...
Narek Bojikian's user avatar
5 votes
Accepted

What is the purpose of learning propositional logic

Briefly, one can't learn AI without it. Some of the main content areas of AI are based on logic: knowledge representation, planning, natural language semantics and reasoning. Have a look at the ...
ShyPerson's user avatar
  • 925
4 votes

About randomness and minmax algorithm with alpha beta pruning

It's neither faster nor slower, since it depends on your order. Your order might be the best possible order, in which case randomness hurts; or it might be the worst possible order, in which case ...
Yuval Filmus's user avatar
4 votes
Accepted

What method of collective recogintion to use for digits recognition?

The state of the art for digit recognition does not use collective recognition, competence areas, ensembles, or any of the other ideas you propose in your question. Instead, the state of the art for ...
D.W.'s user avatar
  • 161k
4 votes
Accepted

Using AI / Machine learning to find the most time and space efficient solutions to an algorithm

No. With all the hype about AI/Machine learning, sometimes people forget that there are known limitations to computers, which can be proven, so it doesn't matter how fast your computer is, how ...
Ariel's user avatar
  • 13.4k
4 votes
Accepted

How can image processing neural networks be effectively trained?

Yes. Typically a very large data set is required: tens or hundreds of thousands of labelled images, or perhaps even more. No, 100 images almost certainly won't be enough. Just running over the same ...
D.W.'s user avatar
  • 161k
4 votes

Heuristics for the $n$-puzzle

First of all, a heuristic is said to be admissible if and only if $h(n)\leq h^*(n)$ for every state $n$, where $h(n)$ is your heuristic function and $h^*(n)$ is the cost of an optimal path from $n$ to ...
Carlos Linares López's user avatar

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