[invincing]

Late to the party, but the proof requires integers with infinite amount of bits. With real-life programming languages there's limited number of bits in integers, and this means that the proof doesn't work with any real-life language such as Javascript.

Consider just 2-bit integers (because it makes this easy, in real life the number of bits is of course larger). If i in F(i) has just 2 bits (possible values thus are 0,1,2,3), each Fn(i) can be represented by a table of four 0/1 values. The function just returns the value at the table in the input index. This also means that there are only 16 possible functions Fn() for a 2-bit input (as return values 0 and 1 can be combined in 16 ways in the 4-entry table). There may be infinite amount of lexically different functions, but based on what the functions actually do, most of them are duplicates that provide the same functionality.

All possible functions with 2-bit input value, and their respective 1-bit return values can be written out to a table: input: 0 1 2 3 result: f0: 0 0 0 0 f1: 1 0 0 0 f2: 0 1 0 0 f3: 1 1 0 0 f4: 0 0 1 0 f5: 1 0 1 0 f6: 0 1 1 0 f7: 1 1 1 0 f8: 0 0 0 1 f9: 1 0 0 1 f10: 0 1 0 1 f11: 1 1 0 1 f12: 0 0 1 1 f13: 1 0 1 1 f14: 0 1 1 1 f15: 1 1 1 1

The point is that even if a function is defined by a completely different algorithm (and thus lexically different), it can be reduced to a table lookup, where the size of the table is defined by the number of bits in the input. For instance from the functions above, isOdd() is the same as f10() and isPrime() is the same as f12().

Now, if we take any function above, we can find another function in the table that provides correct answers for 1 - Fn(i). For instance for f12() we have results 0 0 1 1, so we need a function that provides results 1 1 0 0. This is f3(). This is clearly a function that is already in the set.

If there are more bits than 2 available for i, the amount of different functions just grows, but is still limited in the same way as with a 2-bit input. So in order for the proof to work, input variables need to have infinite number of bits.

[smadge]

First, there are many language who’s default integer type are not fixed bit width. For example Haskell and Python can represent arbitrarily large integers out of the box, limited only by available memory. Second, it is not too difficult to implement these “big integers” in any language. For example, I think java has something called a BigInteger class. Arguably if your “integer” type has fixed but width, it’s categorically not an integer. Third, two of the major underlying theoretical models of computation, Turing machines and Churche’s lambda calculus, allow arbitrary “memory” sizes and arbitrarily large integers. For example the universal Turing machine is imagined as operating over an infinitely long ticker tape. The objection you raise is a theoretical nonissue and I give the author some leeway to make this concept more accessible.

[invincing]

I think it's important to know when a theoretical framework can be applied to the full extent and when the real-life situation is actually a subset that behaves differently.

In this case the problem is solvable within the subset presented by the JavaScript language, but there are other cases where applying theory directly to real life constructs without considering the differences can lead to buggy code. For instance floating point numbers come to mind immediately.

I agree that discussions like this are sidetracking the whole point of a good article, but in order to avoid that, I'd use pseudo-code instead of a real language for presenting concepts like this.

[petermcneeley]

Yes it is actually the infinite that is at the core of all these problems. Same with the incomputability of https://en.wikipedia.org/wiki/Kolmogorov_complexity . If you simply think in terms of bits (the finite) none of these problems exist as one can simply search all permutations.