Program Synthesis with Large Language Models

Re:Program Synthesis with Large Language Models by mjburgess on Wednesday August 18, 2021 @04:10AM (#28218741)

> it's a little unsatisfying from the perspective of studying intelligence

This power-law behaviour is exactly what you get when modelling a non-computable function.

Eg., consider approximating the mean of sin^2(x) over -pi to +pi.

If you sample x 10^s times (s = 1, 2, 3, ...) the difference from the non-computable analytic answer (0.5) scales log-linear (ie., power-law).

    { pwr : 
            np.log(0.5 - (
                np.sin(np.linspace(-np.pi, +np.pi, 10**pwr)
            ) ** 2).mean()) 
        for pwr in range(1, 8) 
    }

It is my view that intelligence isn't computable, and that any approximation method to some layer of intelligence will run-up against this problem.

[ Parent | on HN ]

Re:Program Synthesis with Large Language Models by nextaccountic on Wednesday August 18, 2021 @10:25AM (#28221345)

I think you're mixing up terminology here, because sin^2(x) is computable.

I mean, if there is a process to progressively give better estimates of the output of a function, then this function is computable.

[ Parent | on HN ]

Re:Program Synthesis with Large Language Models by mjburgess on Wednesday August 18, 2021 @10:43AM (#28221634)

sine is a real-valued function

There is a computable version for computable inputs, ie., we ask "what is sin(x)?" for some computable-number x_computable.

But there is no computable version for a non-computable real number, x_real.

[ Parent | on HN ]

Re:Program Synthesis with Large Language Models by nextaccountic on Wednesday August 18, 2021 @12:05PM (#28223209)

Thank you for the clarification.

> But there is no computable version for a non-computable real number, x_real.

That's true[0]. But consider that you will never receive something non-computable as input to a program, ever. (if you're allowed to approximate the input until you have enough digits to compute what you need, then the input is computable)

Really, I think the best way to view sin(x) is as a function that receives a stream of digits 0.2345345323.. and returns a stream of digits 0.0040933884... - this computable version of sine completely captures every thing we could possibly do with it in a program. Operating with floating point numbers, then, is just mostly truncating the input and output stream.

[0] At least in classical logic; in intuitionistic logic, sin : Real -> Real is computable and is equivalent to this idea of receiving and returning streams of digits.

[ Parent | on HN ]

Re:Program Synthesis with Large Language Models by mjburgess on Wednesday August 18, 2021 @01:02PM (#28224081)

> completely captures every thing we could possibly do with it in a program

Yes, but this is far less than nature can do with it -- which is my point, that discrete computation is extremely limited.

[ Parent | on HN ]

Re:Program Synthesis with Large Language Models by nextaccountic on Thursday August 19, 2021 @04:40AM (#28231666)

Oh, I see. Then we're in agreement, our digital computers are less powerful than analog computers with unlimited precision. What we don't know if such analog computer could exist -- or even if the universe is equivalent to one.

That is, we don't know if nature is actually continuous. Perhaps spacetime becomes discrete in the Planck scale or something like that (I know past attempts have been unsuccessful, but still, it might be). But if nature is continuous, there is probably a fundamental limitation on harnessing those precision bits past a certain limit. Nature's continuous variables might have enough symmetries as to make it Turing-complete. In this case, computation with full real numbers wouldn't ever happen in this universe.

I mean, if it happens, the Church-Turing thesis would be false, and the consequences would be far more strange.

[ Parent | on HN ]