Hacker News Reader

Comment by Legend2440 | Hacker News Reader

Here's a counterexample. Suppose I create a simple neural network that computes f(x) = x^2 + c (where x and c are complex numbers) and then I run it as an RNN. This RNN will compute the mandelbrot set, which can't be represented by a lookup table.

You can't even know if the RNN will halt for a given input. Neural networks are stronger than lookup tables, they are programs.

View on HN

Every computable function can be represented by a (possibly infinite)¹ lookup table.

Computer programs can only compute computable functions. Therefore any computer program is (in theory) equivalent to a table lookup.

¹ For finite inputs, the lookup table can be finite, and for infinite inputs, the lookup table can be infinite but still countable, as the set of computable functions is countable.

This table is not computable. If you had this table, you could solve the halting problem by simply looking up whether the program produced an output.

You've just restated the halting problem.

Nobody claimed that there is an algorithm to translate arbitrary programs into an equivalent lookup table. (Because that's the exact same proposition as stating that there is a program that can compute whether an arbitrary program halts when executed).

The point is: Any specific program can be translated into a lookup table. Computer programs and lookup tables are equivalent!

You claimed that computer programs are somehow "more powerful" than lookup tables. That's just plain wrong. They're exactly equivalent in "power".

I am sorry to be this blunt but this is really utter and complete nonsense. The phrase that the mandelbrot set can't be represented in a lookup table is as such true but that is because nothing that you do with finite precision numbers can represent the mandelbrot set because it essentially is an inifinte object. The function f(x) = x^2 + c as an RNN can also not compute the mandelbrot set if the numbers it uses are of finite precision. That is exactly the same limitation that the lookup table also faces so there is no fundamental difference between the two.

We can give them both infinite precision, you still can't build a lookup table of the mandelbrot set.

The mandelbrot set is essentially a map of the halting behavior of a specific program. You can't know whether or not the program will halt for a given input, and so cannot build the lookup table. Programs are stronger than input-output mappings.

Infinity is really hard to reason about, are you sure about that?

(For all I know you're a PhD in transfinites, your profile says nothing).

Infinity (of the various kinds) is well understood (see Cantor etc).

The Halting Problem is a central result in computer science, again well understood (especially here I would think!)

Their comment is correct.

I see you are a fan of flying disembodied brains, but this time without a universe surrounding the brain.

Reply on news.ycombinator.com