News for hackers. Stuff that matters.
Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by littlecranky67 on Thursday June 17, 2021 @04:08AM (#27537240)
Veritasium recently released a very good video that explains Gödels incompletenes theorem such that even I could understand it: https://www.youtube.com/watch?v=HeQX2HjkcNo
Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by beltsazar on Thursday June 17, 2021 @05:15AM (#27537638)
That Veritasium's video is great! I'd also recommend Computerphile's 3-part video series (~10 mins each) which tells the history of undecidability and the incompleteness theorem:

https://www.youtube.com/watch?v=nsZsd5qtbo4

https://www.youtube.com/watch?v=FK3kifY-geM

https://www.youtube.com/watch?v=lLWnd6-vSGo

Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by rottc0dd on Thursday June 17, 2021 @05:47AM (#27537871)
There is a little great book called "Godel's proof" by Nagel and Newman[1]. And definitely requires some focus but readable nevertheless.

[1] https://www.amazon.com/G%C3%B6dels-Proof-Ernest-Nagel/dp/081...

Edit : removed a line

Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by ruste on Thursday June 17, 2021 @09:11AM (#27539190)
I second this! I spent a few days of summer vacation in highschool slowly working my way through this and it was mind expanding.
Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by alok-g on Thursday June 17, 2021 @03:17PM (#27543392)
A good book as such. However, whereas the authors claim that they outline the proof in chapter 6, that chapter fell short of it with key aspects of the proof missing. Overall, I was disappointed.
Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by chriswarbo on Thursday June 17, 2021 @08:37AM (#27538907)
I knew Gödel's (first) incompleteness theorem pretty well already, but I really enjoyed how much that video managed to get across without getting too bogged down.

One thing I'd like to see in a companion video would be an explanation of why Turing machines represent computation. That video (like many others) skims over the why, and only talks about what they can/can't do after we've already decided to use them.

Turing's 1936 "On Computable Numbers" paper gives a nice philosophical justification for his model, which (from my reading) boils down to the following:

- Mathematicians can do their work within a finite volume of space (their brain, or a room, or the whole Earth if we want to be conservative). Also, they could (in principle) do their work using only written communication, on standard pieces of paper, each of which also has a finite volume.

- Finite volumes can only have finitely-many distinguishable states (having infinitely many states would require them to be infinitesimally similar, and hence indistinguishable from each other within a finite amount of time)

- Hence we can label every distinguishable state of a brain with a number; and likewise for every distinguishable piece of paper (at least in principle)

- Since these are both finite, any mathematician's behaviour could (in principle) be completely described by a table detailing how one state (brain + paper) leads to another

- Given such a table, the actual content of the states (e.g. the wavefunctions of particular protons, the electrical potential of particular synapses, the placement of ink molecules, etc.) is irrelevant for the behaviour; only the transitions from one numbered state to another matter

- Hence we could (in principle) build a machine with the same number of states as one of these tables, and the same transitions between the states, and it would exactly reproduce the behaviour of the mathematician

This is the philosophical justification for why a (Turing) machine can calculate anything a human can (in fact, the same argument shows that a Turing machine can reproduce the behaviour of any physical system).

However, this is still a rather hand-wavey "in principle" thought experiment about unimaginably huge numbers. Turing managed to take it further.

For simplicity we assume all the papers are arranged in a sequential "tape", we'll call the distinguishable states of the papers "symbols" and those of the mathematician/machine "states":

- One thing a mathematician can do is read a tape with one of these tables written on it, followed by a sequence of numbers representing the symbols of another tape, and emulate what the described machine would do when given the described tape (i.e. they could keep track of the current state and tape position, and look up the transitions in the table, to see what would happen)

- Since a mathematician can emulate any given table (in principle), so can a machine. This would be a "universal machine", able to emulate any other. (The video talks about such a machine, in the proof that the halting problem is undecidable)

So the question becomes: how unfathomably complicated would such a universal machine have to be?

- These transition tables and tapes can be very big, and may contain very large numbers, but we can write them down using only a small alphabet of symbols, e.g. "start table", "new row", "the digit 7", etc.

- Reading a sequence of such symbols, and emulating the described machine, can get tricky. Turing described a universal machine "U", but he did so in a rather indirect way, which also turned out to have some mistakes and glaring inefficiencies. Davies later worked through these and ended up with an explicit machine using only 147 states and 295 symbols.

Hence we can use a machine with only a few hundred states to exactly reproduce the behaviour of any mathematician (or any physical system), as long as it's given an appropriate description (i.e. "software"). Later work has found universal Turing machines with only 4 states and 6 symbols.

One reason Turing's justification for his model is important, rather than just proposing the model and seeing what happens (like in the video), is that Alonzo Church had already proposed a model of computation (called Lambda Calculus), but didn't have such a justification.

Gödel himself dismissed Lambda Calculus, proposing his own system (General Recursive Functions) as a better alternative. When Church proved they were equivalent, Gödel took that as reason to dismiss his own system too! Yet Turing's argument did convince Gödel that a fundamental limit on computation had been found. Turing proved his machines are also equivalent to Lambda Calculus, and hence General Recursive Functions; so all of these proposed models turned out to be 'correct', but it was only Turing who could explain why.

Personally I consider this reduction of physical behaviour to transition tables and then to machines, to be the main reason to care about Turing machines. Proving the undecidability of the halting problem was also a great achievement of Turing's 1936 paper (as shown in that video), but that can also be explained (I would argue more easily) using other systems like Lambda Calculus.

Without Turing's justification of his model, undecidability comes across as simply a flaw. Sure Turing machines may be (distantly) related to our laptops and phones, but if we found a better model without this 'undecidability bug' we could make better laptops and phones! Turing's argument shows that there is no better model (just equivalents, like Lambda Calculus).

Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by Rioghasarig on Thursday June 17, 2021 @11:11AM (#27540422)
> This is the philosophical justification for why a (Turing) machine can calculate anything a human can (in fact, the same argument shows that a Turing machine can reproduce the behaviour of any physical system).

I don't think this assertion follows. I don't think an argument like this can work without delving further into reasonable description of a "physical system".

If you just just use the mathematics we employ to describe physical systems unreservedly it is possible to construct "physical systems" that exhibit non-computable behavior. For instance you can have computable and continuous initial conditions to the wave equation that produces a solution that is non-computable. See : https://en.wikipedia.org/wiki/Computability_in_Analysis_and_...

I think it's important to emphasize that Turing stated his arguments in regards to "effective procedure" (which I see you mention in a different post). I don't think the substitution of "effective procedure" with "physical system" is justified.

Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by chriswarbo on Thursday June 17, 2021 @01:07PM (#27541894)
> For instance you can have computable and continuous initial conditions to the wave equation that produces a solution that is non-computable.

Thanks, that's a really nice example which I hadn't come across before (or at least not spent too much time studying). I may have to refine the language I use in future; although a cursory look seems to be compatible with my own understanding (my mental model is roughly: "if we found a halting oracle, we would have no way to tell for sure")

> I think it's important to emphasize that Turing stated his arguments in regards to "effective procedure" (which I see you mention in a different post). I don't think the substitution of "effective procedure" with "physical system" is justified.

Yes, Turing did not say as much (at least in his 1936 paper). He was essentially abstracting over 'whatever it is that a person might be doing', in an incredibly general way. Others have since taken this idea and applied it more broadly.

Another useful caveat is that Turing machines are framed as (partial) functions over the Natural numbers. It's quite a leap from there to a "physical system". An obvious example is that no matter how cleverly we program a Turing machine, it cannot wash the dishes; although can simulate the washing of dishes to arbitrary precision, and it could wash dishes by controlling actuators if we decided to attach some (but even that would run into problems of time constraints; e.g. if calculating the first instruction took so long that the water had evaporated).

Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by wizzwizz4 on Thursday June 17, 2021 @05:32PM (#27544705)
The problem with your assumption is that you're assuming there are a finite number of states. There might be an uncountably infinite number of states, for instance if the states were the reals between 0 and 1.
Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by chriswarbo on Saturday June 19, 2021 @06:59PM (#27565311)
Which assumption are you referring to? If it's about the states in a finite region, note that I specifically limited this to distinguishable states.

Whether or not a finite region can have an infinite number of states (countable or otherwise) is irrelevant; we can only distinguish finitely many in finite time. Two states being indistinguishable means they'll give rise to the same output behaviour (e.g. from a mathematician in a room, carrying out some procedure).

Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by meroes on Thursday June 17, 2021 @09:00AM (#27539101)
Where in there did Turing prove computation can "exactly reproduce the behavior to...(any physical system)"? Because we humans seem to be able to describe and write down the behavior of any physical system? I'm not sure that jump is airtight.

I'm not sure we can say this part even though we might believe it to be true. I mean maybe now we can since we have no deeper theories than quantum field theories, and we can posit all of physical reality reduces to QFTs and GR and simulate all of QFT computationally either with quantum computers (in real time) or classical (not in real time + need a random number generator). But the we'd still have computational limits by which observables we can measure and how big of computations we can run (think size of computer limited by black hole density for one crude example - although I guess a blackhole could be used as a quantum computer. So then I'd say the speed of light is the other main limit, we've already lost the information to run certain calculations to the depths of space).

And to focus back in on the random number generator requirement for classical to simulate quantum...nothing fundamentally random can be simulated classically in principle. Yet randomness is needed to describe the most basic layer of reality. I can't get true randomness from classical no matter what.

Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by chriswarbo on Thursday June 17, 2021 @09:41AM (#27539452)
> Where in there did Turing prove computation can "exactly reproduce the behavior to...(any physical system)"? Because we humans seem to be able to describe and write down the behavior of any physical system?

Turing's scenario essentially applies to a person in a room, with an unlimited amount of paper (this could be a movable tape extending through the walls, to prevent the room filling up with paper!).

However, the same argument works if we replace the person with any other physical system (e.g. some mechanical device, or some physics experiment), and replace the room with any finite region of space (e.g. the Milky Way galaxy).

I don't remember Turing himself making this argument (let alone in his 1936 paper), but it's known as the "physical Church-Turing thesis" https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis#V... (the Church-Turing thesis is the argument that all 'effective methods of calculation' can be carried out by a Turing machine)

As for your points about quantum physics, etc. that's certainly true, and it's why the Church-Turing thesis isn't a theorem (and can't be, since we can never know if any particular model of reality is correct). However, it's certainly a valid physical law, akin to nothing moving faster than light, etc. i.e. it's empirically true, theoretically sound, and we have no better explanation for the moment.

Perhaps its origin in mathematics, where it is a second-class citizen compared to provable theorems, prevented the Church-Turing thesis getting the recognition it deserves, e.g from physicists.

Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by foxes on Thursday June 17, 2021 @10:30AM (#27539962)
Well I might add the quantum complexity-theory version of the Church–Turing thesis.

I believe that quantum computation is a richer more powerful theory. In essence BQP is a superset of BPP in your link.

I think this happens with all sorts of mathematical objects. Non commutative algebra is much richer than commutative algebra. There are also more interesting non commutative things than just deformations of classical objects. Its the classical commutative case that is the weird limit.

Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by chriswarbo on Thursday June 17, 2021 @11:02AM (#27540318)
Yeah, there are all sorts of layers we can add, especially regarding complexity (i.e. resource usage limits, rather than simple yes/no questions of decidability).

It's interesting to consider P = NP as a physical law, although that's certainly more tenuous than the Church-Turing thesis, etc.

Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by lurquer on Thursday June 17, 2021 @02:44PM (#27543011)
Interesting post.

Can you please flesh out the following? I don’t quite follow it..

> having infinitely many states would require them to be infinitesimally similar, and hence indistinguishable from each other within a finite amount of time

Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by chriswarbo on Thursday June 17, 2021 @05:52PM (#27544845)
Sure. Let's take a finite region, like a room. We don't want to get too bogged down in the details of human psychology, anatomy, etc. so we'll stick to something very low-level like particle physics (which, in principle, can describe a person in exact detail). One state of this region is that it's completely empty (maybe quantum effects rule that out, but we can still include it if we're being conservative ;) ). Another state could have, say, a single electron, at some position we'll call (0, 0, 0). Another could have a single electron at position (0, 0, 1). Another has an electron at (25, 5, 3) and a proton at position (0, 0, 0). And so on.

Let's consider the states which just contain a single electron, somewhere in the room (I'm not bothering with quantum effects, but we would do the same thing just in Hilbert space instead of 3D space). The region is finite, so the coordinates of this electron are bounded: if the boundaries are at, say, 0 and 100 in each axis, then putting the electron at position (101, 0, 0) would be the same state as the empty one we started with (since the electron is outside the region we care about, and there's nothing else).

Now let's say we do some measurement of this electron's position, which is only accurate to whole number coordinates. That gives us 100^3 = 1,000,000 distinguishable states with a single electron. We might imagine all sorts of different states 'in between', but they can't affect that measurement due to its limited resolution.

If we increase the resolution of our measurement by 10, we get 10^3 times as many distinguishable states; another factor of 10 gives 10^3 times as many states again; and so on. However, regardless of how finely we can resolve the electron's position, we can only distinguish between finitely-many states. Any differences finer than that limit are irrelevant to the measurement, and hence to any behaviour that depends on that measurement.

If we could resolve between infinitely-many positions for the electron, that would require distinguishing between states which are infinitesimally-close together, i.e. on an infinitely-fine grid; this would require distinguishing between two numbers whose decimals only differ after infinitely many digits. This doesn't seem like a reasonable capability.

The same principle applies when we have two electrons in the room, or trillions, or any combination of electrons, protons, photons, etc. in any arrangement we like.

A similar thing happens when we reach really large numbers too, e.g. trying to put as many particles in the region as we can: at some point the relative difference between, say, a googolplex and five particles versus a googolplex and six particles becomes too small to distinguish. There will eventually be a limit. (This is like the resolution problem, but instead of adding decimal places to the right of each number, we're adding factors of 10 to their left)

One way to get around this problem of limited resolution is to avoid an explicit 'measurement', and instead have the region itself behave differently for different states. A good example is chaotic behaviour, where tiny changes in an initial state will grow exponentially until those differences eventually become distinguishable. However, the infinitesimally-similar states described above will remain infinitesimally close for all finite lengths of time; in order to distinguish between them, we would need to wait an infinite amount of time.

Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by lurquer on Thursday June 17, 2021 @10:24PM (#27546764)
Ah. I hadn’t thought of that.

So putting aside Plank and all the experimental stuff, even on a philosophical level there are problems with thinking of space as continuous. For, that with which we measure space is necessarily discrete and the time-frames in which we measure are necessarily finite. So, even if space was continuous, two ‘states’ that are infinitesimally similar could for ALL practical purposes be considered identical.

Is that it?

Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by chriswarbo on Saturday June 19, 2021 @08:43PM (#27565949)
Pretty much.

As a far less formal analogy, it's similar to how people complain that digital audio in general has lower quality than analogue, just from a discrete vs continuous standpoint. When in fact there's no limit to the quality of a digital representation (if we liked, we could store a gigabyte per sample, or a petabyte, or whatever). Yet we can always draw the line somewhere, beyond which there are no meaningful distinctions.

Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by 0x0203 on Thursday June 17, 2021 @09:26AM (#27539315)
I know I'm pretty inept when it comes to this subject, but can someone help me understand how the first three points of Turing's philosophical justification listed above can be true? For example, in computing the sequence of n values of an infinite series or the first n digits of pi, how can the claim be made that this can be done in a finite amount of space or with a finite number of states?
Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by mcguire on Thursday June 17, 2021 @02:39PM (#27542944)
Turing's machine includes an "infinite" tape. The number of states, the state transitions, and the number of symbols are finite, but an unbounded number of symbols can be written, one to a cell, on the tape.
Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by chriswarbo on Thursday June 17, 2021 @10:43AM (#27540109)
We're allowed an unlimited amount of paper, but each piece has a finite size, and hence each piece is in one of only finitely-many distinguishable states. Turing called these piece-of-paper-states "symbols", and arranged the pieces of paper in a "tape" of unlimited length (a stack of sheets, or a library of books would also work; but moving between the pieces would be more complicated).

In fact, we only ever need 2 symbols, e.g. 0 and 1. This is because any set of symbols can be replaced by a set of numbers, and those numbers can be written in binary (with a fixed width, to avoid needing 'spacers'). This can require a lot more machine states, since those states allow the machine to 'remember' the bits it's read so far (e.g. if we're using 8 bits at a time, then we need enough states to "remember" what the first 7 bits were as we're reading the 8th).

For a calculation like pi, we can use the tape to (a) write down the digits (or bits) of pi, and (b) keep track of intermediate variables needed for the calculation. One simple approach to keeping track of intermediate variables is to store them in order on the tape, where each variable is a sequence of 1 symbols, separated by 0 symbols. For example a tape like: 111010010 represents four variables with values 3, 1, 0 and 1 (the number of 1s we see before we hit a 0). This actually corresponds to Peano arithmetic, if we use the symbols S and Z instead like SSSZSZZSZ.

An algorithm which spits out digits of pi forever (e.g. http://www.cs.ox.ac.uk/people/jeremy.gibbons/publications/sp... ) could work by moving its 'variables' section further and further to the right, allowing the digits of pi to accumulate, e.g.

    Start
    
    ^

    Initialise variables and output/variables separator
    |VARIABLES

    Move variables to make space for next digit
    _|VARIABLES

    Calculate and write next digit
    3|VARIABLES

    Move variables to make space for next digit
    3_|VARIABLES

    Calculate and write next digit
    31|VARIABLES

    and so on
Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by mensetmanusman on Thursday June 17, 2021 @10:18AM (#27539832)
It might be because pi isn’t infinite in practice. E.g. we could use all the available energy in the universe and only calculate up to a finite digit (ignoring the information storage issue!).

Whether the abstract infinite pi ‘exists’ is up for metaphysical debate :)

Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by chriswarbo on Thursday June 17, 2021 @10:48AM (#27540150)
Here is pi, written as a number to infinite precision (from http://davidbau.com/archives/2010/03/14/python_pipy_spigot.h... ):

    def pi_decimal_digits():
      q, r, t, j = 1, 180, 60, 2
      while True:
        u, y = 3*(3*j+1)*(3*j+2), (q*(27*j-12)+5*r)//(5*t)
        yield y
        q, r, t, j = 10*q*j*(2*j-1), 10*u*(q*(5*j-2)+r-y*t), t*u, j+1
If you mean that pi can't be written as a number to infinite precision using place-value notation (as opposed to a more useful notation like Python) then I agree that only a finite prefix can ever be observed.
Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by lmm on Thursday June 17, 2021 @10:50PM (#27546901)
What you've written is not pi, it's a procedure for computing pi. Python expressions are not a notation, they fail basic requirements for a reasonable notation (for example you cannot generally determine whether two Python expressions are equal or not).
Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by mietek on Friday June 18, 2021 @04:58AM (#27548585)
You may find it interesting to learn that one cannot generally determine whether two real numbers are equal or not: equality on real numbers is undecidable.
Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by lmm on Friday June 18, 2021 @05:03AM (#27548606)
I'm well aware. It's also the case that there is no good notation for the real numbers; in particular since any given notation system can only represent countably many distinct entities, almost all real numbers will be are unrepresentable in that notation system. Therefore the notion that the full set of reals actually exists is extremely dubious.
Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by mcguire on Thursday June 17, 2021 @02:42PM (#27542982)
Note that the Python version of pi requires an unbounded amount of memory and, more importantly, an infinite amount of time to produce pi to infinite precision.
Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by Kranar on Thursday June 17, 2021 @10:42PM (#27546857)
Not at all, the reason you may think so is that you're very used to representing numbers using a base 10 number system and in that system it is inherently impossible to represent pi. But if you change how you represent numbers, you can represent pi exactly. What OP did was represent pi using a syntax inspired by a programming language, which is just as valid a number system as any other formal representation as far as correctness goes, although of course as a human I likely would not wish to express most of my use cases involving numbers using a full blown programming language.

That said, one can perform all of arithmetic using that system and represent any property of numbers that could be represented otherwise.

Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by chriswarbo on Thursday June 17, 2021 @04:38PM (#27544299)
> Note that the Python version of pi requires an unbounded amount of memory

Really? I measure it as exactly 200 bytes (not counting the 4-space indentation that HackerNews requires, and not including a trailing newline)

> and, more importantly, an infinite amount of time to produce pi to infinite precision

I can see it right now, with infinite precision. If it's taking an infinite amount of time to show up I'd contact your ISP ;)

Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by mcguire on Friday June 18, 2021 @04:37PM (#27554753)
Ah, I see where you are going with this. However, I can offer a version which, without loss of generality, gives another 200-to-1 compression (not counting UTF-8 multibytes): π.

There it is, in all it's infinite splendor.

Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by mensetmanusman on Thursday June 17, 2021 @06:06PM (#27544948)
Also, pi = C/d

in geometry notation :)

Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by mensetmanusman on Thursday June 17, 2021 @10:21AM (#27539865)
I’ve wondered recently whether the brain can be represented by a Turing machine if our computation mechanisms utilize something like back propagation through time via quantum effects.

Maybe we will make progress in our understanding this millennia :)

Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by chriswarbo on Thursday June 17, 2021 @11:00AM (#27540287)
Quantum physics can be represented and calculated by Turing machines. There are many ways to do this, depending on preference: via symbolic algebra, via probabilistic inference, via random/pseudorandom numbers, via non-deterministic functions, etc.

Note that quantum computers are no more powerful than Turing machines; although it's thought they might be faster at certain tasks. For example, we know how to factorise integers quickly using Shor's algorithm on a quantum computer, but we don't yet know a quick algorithm for factorising integers on a classical computers. We can still factorise integers on a classical computers: we can do it with a non-quantum algorithm, or we can even do it by emulating a quantum computer and using that emulator to run Shor's algorithm (in this case the emulation is so slow that it exactly cancels out the speedup from Shor's algorithm).

Backpropagation through time is also a pretty simple algorithm, which is already implemented on classical computers.

Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by meroes on Thursday June 17, 2021 @12:51PM (#27541690)
> Quantum physics can be represented and calculated by Turing machines.

1) Where does the randomness of QM come in though? You need a random number generator alongside your Turing machine.

We coud debate that one can never prove true randomness as it may always be due to some deeper determinism. But if we take the wavefunction of QM as complete, which Many Worlds does - the most compsci-like interpretation - then randomness is fundamental according to theory.

I can have all the TM's I want, but I still need this extra component. Just like the human Turing machine could have all the pen and paper and math in the entire universe and beyond, a human can't produce a truly random number (or can we, then we get into a debate about true free will and whether free will can produce a "random" number).

2) Let's say we instead use quantum computation instead of classical. There are still physical systems we can't "compute", like the state of the entire observable universe, the state of the entire universe, or anything requiring information that has forever left our light cone. I know TM's and quantum versions of TM's are infinite, but they can't bypass the speed of light. So we need some softer version of saying all of physical reality is computable imo.

Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by Kranar on Thursday June 17, 2021 @10:45PM (#27546873)
> But if we take the wavefunction of QM as complete, which Many Worlds does - the most compsci-like interpretation - then randomness is fundamental according to theory.

MWI is an entirely deterministic interpretation of quantum mechanics. Absolutely no randomness is involved which is one of its most appealing properties.

Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by chriswarbo on Thursday June 17, 2021 @01:50PM (#27542349)
> Where does the randomness of QM come in though?

That's why I said it's up to your own preference.

It's interesting that you mention a many-worlds approach, since that doesn't actually involve any randomness. Rather than choosing a single result probabilistically, many-worlds keeps them all. This can be represented quite nicely with what I referred to above as 'nondeterministic functions', i.e. functions which may return multiple values (in some sense, those values are literally the "worlds"). This would look like a logic language a la Prolog, but wouldn't be restricted to depth-first traversal: it could run breadth-first (very slow), concurrently (nice in principle, but would swamp any finite machine with overheads), or iterative deepening (probably the nicest implementation IMHO). Haskell programmers would call this a "breadth-first list monad" (AKA LogicT, AKA Omega). Instead of "returning multiple values", we could also do a continuation-passing transform and invoke the continuation multiple times (concurrently).

This would run exponentially slowly, but that's a whole separate issue ;)

> We coud debate that one can never prove true randomness as it may always be due to some deeper determinism.

We could get a Copenhagen-like approach by doing the same as above, but only returning one of the results, chosen "at random" according to the square of the wavefunction (plus some hand-wavey Copenhagen-craziness, like defining whether or not Wigner's Friend is an 'observer')

When it comes to "randomness" my own approach is to mentally substitute the word "unpredictable", since it tends to be more enlightening. Turing machines can certainly produce results which are "unpredictable", in the sense that the only way to know what will happen is to run the program; in which case that's more like a (repeatable) observation rather than a prediction. (BTW I also think that's a nice resolution of the "free will" paradox: my behaviour may be predicted by observing what an exact copy of me does; but it was still "decided by me", since that copy essentially is "me")

In any case, the outcome of a Turing machine using some pseudorandom algorithm is indistinguishable from "quantum randomness". There is certainly a limit to the unpredictability of any pseudorandom events (given by its Kolmogorov Complexity, which is upper-bounded by the Turing machine's program), but on the other hand I think it's quite presumptuous to think "quantum randomness" has infinite Kolmogorov Complexity.

> There are still physical systems we can't "compute", like the state of the entire observable universe, the state of the entire universe, or anything requiring information that has forever left our light cone.

That's a very different question, since it involves how we choose what to put on the tape, rather than what a Turing machine is capable of computing. It's like criticising a genie for being unable to grant a wish, when in fact it's we who can't think of what to ask for.

Besides this, there is a way for a Turing machine to compute the whole universe, including what's outside our visible lightcone: we simply run every program. That's actually a pretty straightforward task (and remarkably efficient), e.g. see the FAST algorithm in section 9 of https://people.idsia.ch/~juergen/fastestuniverse.pdf

Note that if we run such a program, there is no way to know which of the outputs corresponds to our universe. However, our ignorance of where to look does not imply that such a Turing machine has not computed it!

Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by mensetmanusman on Thursday June 17, 2021 @04:32PM (#27544248)
” Turing machines can certainly produce results which are "unpredictable", in the sense that the only way to know what will happen is to run the program.”

This doesn’t seem true since all predictions are ‘running the program’

Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by chriswarbo on Thursday June 17, 2021 @04:49PM (#27544403)
Not necessarily; lots of systems have 'shortcuts', e.g. I can predict the result of sin(1000000τ) will be 0, without anything physical/virtual having to wiggle up and down a million times. Lots of systems can be described by equations involving a time variable 't', where we can set t = whenever we like, then solve the equation to get the predicted value.

When a system is Turing-complete, equations like this will inevitably involve some expression with t-1; and solving that involves some expression with t-2; and so on back to the initial condition. Hence there's no 'shortcut' (this is a consequence of Rice's theorem BTW, which itself is a consequence of the halting problem).

Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by mensetmanusman on Friday June 18, 2021 @09:29AM (#27550059)
“ e.g. I can predict the result of sin(1000000τ) will be 0, without anything physical/virtual having to wiggle up and down a million times. “

This seems to still involves ‘a program’ in that there are foundational mathematical principals that build your confidence/logic that the periodicity of sin(x) is so well defined that any even integer multiple of pi will be zero. e.g. you could write out the logical ‘programatic’ steps that would also teach a math newbie how to make the conclusion you just made about the sin() function.

Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by chriswarbo on Saturday June 19, 2021 @08:52PM (#27566001)
I agree, but such a "program" wouldn't necessarily look/act anything like the "program" 'sin(1000000τ)'.

What's interesting about systems like Turing machines is that the "program" is a specific, isolated thing like a tape of symbols. In contrast, those "foundational mathematical principles" you mention are more of a diffuse web, with lots of interchangable pieces, all mixed up with unrelated facts. This gives lots of different ways to arrive at the answer. With Turing-complete systems, we always have to come back to the code.

Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by wizzwizz4 on Thursday June 17, 2021 @05:38PM (#27544740)
> Note that quantum computers are no more powerful than Turing machines;

But computers with self-consistent time travel are more powerful. It's perhaps physically possible to construct one of those, depending on whether we ever end up with a more-correct timeless theory of physics that makes different predictions to existing physics.

> Backpropagation through time is also a pretty simple algorithm, which is already implemented on classical computers.

I read “backprop through time” as meaning that you have the result of the backprop at the beginning of the process – that's more powerful, if we're using continuous computation. (With discrete computation, you're right that it's no more powerful.)

Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by ProfHewitt on Thursday June 17, 2021 @09:45AM (#27539491)
There are very simple digital computations that cannot be

performed by a Nondeterministic Turing Machine.

See the following for an example:

https://papers.ssrn.com/abstract=3603021

Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by tsimionescu on Thursday June 17, 2021 @11:01AM (#27540309)
That would be a major revolution to the foundations of computer science if it were true, disproving the Church-Turing thesis. It seems unlikely that such a fundamental, world-shattering result would be so obscure, so I am much more likely to believe it is false.
Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by ProfHewitt on Thursday June 17, 2021 @11:34AM (#27540735)
Do you have any reasoning to back up your belief?
Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by tsimionescu on Thursday June 17, 2021 @04:53PM (#27544426)
As I said, if someone had convincingly proved this, it would shake the field to its core. Since that didn't happen, they can't have convincingly proven this.
Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by ProfHewitt on Thursday June 17, 2021 @06:24PM (#27545103)
Scientific progress does occur!

Recent advances are compatible with a long tradition with

contributions by Euclid, Dedekind, Frege, Russell, Church, Turing, von Neumann, etc.

The following article is in furtherance of the long tradition:

https://papers.ssrn.com/abstract=3603021

Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by jjgreen on Thursday June 17, 2021 @06:45PM (#27545284)
That's 7 times you've linked to that paper in this discussion, going for some kind of record?
Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by ProfHewitt on Friday June 18, 2021 @12:32PM (#27552100)
Have you read the article?

Can you suggest any improvements?

Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by kaba0 on Thursday June 17, 2021 @11:43AM (#27540866)
With all due respect, it would be very hard for me to believe so. For the simplest case, one can trivially create a Turing machine that simulates a CPU, so I’m not sure the digital computation holds any water.
Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by ProfHewitt on Thursday June 17, 2021 @12:09PM (#27541196)
Issue is that a Turing Machine cannot communicate with other Turing Machines in the middle of a computation.
Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by kaba0 on Thursday June 17, 2021 @12:37PM (#27541532)
Let me rephrase: an n-core CPU can be simulated on a Turing machine with eg. time sharing — effectively being able to simulate the Actor model.
Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by ProfHewitt on Thursday June 17, 2021 @02:21PM (#27542726)
Turing Machine can only do cooperative multiprogramming and cannot do time-interrupted scheduling.
Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by kaba0 on Thursday June 17, 2021 @02:35PM (#27542879)
Well, not time-interrupted but there absolutely is a way to schedule n steps of each core, isn’t there? Similarly to how the universal Turing machine is constructed, or how the nondeterministic TM is made deterministic.
Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by ProfHewitt on Thursday June 17, 2021 @02:53PM (#27543120)
Nondeterministic Turing Machine has only bounded

nondeterminism. That is, for a given input a Nondeterministic

Turing Machine can only explore the number of alternatives

bounded by its input. Actors do not have the limitation.

Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by kaba0 on Thursday June 17, 2021 @03:10PM (#27543306)
So unbounded nondeterminism is basically hypercomputation? Then I assume one can write a program for the theoretical Actor model that computes a function on every natural number, is that right? Or that it can solve the halting problem for Turing machines, since if it is stronger then it, the halting problem of TMs is no longer true for them (is replaced by their own halting problem).
Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by ProfHewitt on Thursday June 17, 2021 @03:59PM (#27543916)
An Actor cannot decide the halting problem for program

expressions. See proof in the following:

https://papers.ssrn.com/abstract=3603021

Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by tsimionescu on Thursday June 17, 2021 @05:01PM (#27544481)
Does this difference still hold if time were discrete? I may be out of my depth, but it seems intuitive that if time were discrete, you could enumerate all possible interleavings of actors' actions, and reproduce their behaviors in a Turing machine.
Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by ProfHewitt on Friday June 18, 2021 @12:37PM (#27552163)
Bounded nondeterminism means that there is a bound

determined by initial input for the number of possibilities

that a system can explore given that it must always come

back with an answer. A Nondeterministic Turing Machine has

the property of bounded nondeterminism because it starts in

a global state and from each state there are finitely many

possible successor states. Because the machine must always

produce an answer, each path must be finite and consequently

the total number of states that can be explored is finite.

In the development of a theory of concurrent computation,

Dijkstra remained committed to a global state model of

computation. This commitment gave rise to the “unbounded

nondeterminism” controversy. Digital systems can be

physically indeterminate by making use of arbiters in order

to resolve reception order in communication between systems.

Because of physical indeterminacy, a digital system can have

the property of unbounded nondeterminism in that no bound

exists when it is started on the number of possibilities

that an always-responding digital system can explore.

Consequently, there are digital computations that cannot be

performed by a nondeterministic Turing Machine. Being

restricted to bounded nondeterminism is one the reasons that

the lambda calculus and Turing Machines models are

inadequate for digital computation.

Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by oscardssmith on Thursday June 17, 2021 @12:31PM (#27541469)
This is just false. A Turing machine can emulate multiple Turing machines that communicate with each other.
Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by ProfHewitt on Thursday June 17, 2021 @02:23PM (#27542749)
Turing machine can simulate multiple Turing Machines but cannot implement multiple Turing Machines communicating with each other because there is no means to communicate.
Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by oscardssmith on Thursday June 17, 2021 @05:24PM (#27544637)
But since Turing machines can emulate multiple Turing machines, any problem that can be completed by multiple machines communicating can be solved by 1 Turing machine. As such, the computational power is exactly the same.
Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by ProfHewitt on Thursday June 17, 2021 @06:32PM (#27545179)
As said elsewhere in this posting:

Nondeterministic Turing Machine has only bounded

nondeterminism. That is, for a given input a Nondeterministic

Turing Machine can only explore the number of alternatives

bounded by its input. Actors do not have the limitation.

Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by dahjkol on Thursday June 17, 2021 @04:44PM (#27544356)
Don't need to em every 10th word.
Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by sillysaurusx on Thursday June 17, 2021 @04:55AM (#27537500)
In traditional HN style, I will now thumb my nose at Vertasium's excellent video due to him skipping over how godel came up with the proof.

He built up the whole damn video for that one moment, when he says "And godel went through all this trouble to come up with this card..." and flips over the card. But how godel did it is at least as cool as the proof itself.

I'm mostly being tongue in cheek with the Veritasium nose-thumbing. But if you saw it and want to understand it more deeply (and in my opinion more satisfyingly), I recommend "What Godel Discovered": https://news.ycombinator.com/item?id=25115746

It explains Godel's proof using Clojure. Quite accurately, too.

The thread is also hilarious. Shoutout to the MIT professor who took offense at someone linking to his wikipedia page: "Wikipedia is contentious and often potentially libelous." ... and then you check his wikipedia page, and it's a super positive article about all of his discoveries and life's work.

Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by espadrine on Thursday June 17, 2021 @06:53AM (#27538225)
> Shoutout to the MIT professor who took offense at someone linking to his wikipedia page […] and it's a super positive article about all of his discoveries and life's work.

Carl Hewitt is no doubt a famed and accomplished professor, but why does nobody point out that he is claiming that Gödel’s proof is incorrect[0]?

I already heard of his conviction that “The Church/Turing Thesis is that a nondeterministic Turing Machine can perform any computation. […] [T]he Thesis is false because there are digital computations that cannot be performed by a nondeterministic Turing machine.”[1]. (Which, to be fair, is a strongly related argument to the one that Gödel was wrong.)

I don’t personally know whether he is right, and his digression about millions of people risking death as a result does not inspire confidence, but in my understanding, neither statement is widely accepted.

[0] https://news.ycombinator.com/item?id=25160970

[1] https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3603021

Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by myWindoonn on Thursday June 17, 2021 @07:13AM (#27538358)
I don't want to be a professional Hewitt debunker, but his stance has been ripped to shreds; at this point, he is wrong about Direct Logic refuting Gödel and Turing, and his ActorScript can't be implemented on real machines.
Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by alecst on Thursday June 17, 2021 @09:44AM (#27539473)
I don't know anything about Hewitt or his stance, but I don't feel like this adds a whole lot to the conversation. I mean I can tell that you're sure that he's wrong, but why should the strength of your belief convince me?

It would be helpful if you added some links or some explanation, or just anything beyond what you've written there.

Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by kaba0 on Thursday June 17, 2021 @11:56AM (#27541037)
It’s similar to claiming someone made a perpetuum mobile — extraordinary claims going against basically every mathematician/computer scientist since Gödel require extraordinary evidence. And the result is quasi always that the one claiming, looked over some small but crucial detail.
Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by ProfHewitt on Thursday June 17, 2021 @12:06PM (#27541163)
Veritasium, et. al. overlooked the crucial aspect that

orders on propositions play in maintaining the consistency

of foundations.

Neglecting to include the order of a proposition in in its

Gödel number makes it possible to mistakenly conclude that

the proposition I'mUnprovable exists as a fixed point of a

recursive definition.

See the following for details:

https://papers.ssrn.com/abstract=3603021

Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by espadrine on Thursday June 17, 2021 @12:54PM (#27541721)
Isn’t the order of a proposition included in its Gödel number?

Each proposition is assigned to an increasing prime power, and the increasing list of primes has total order, such that swapping propositions yields a distinct Gödel number.

Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by tsimionescu on Friday June 18, 2021 @03:04AM (#27548043)
I think what ProfHewitt means here (based on other writing I've found, as he is frustratingly low on details in these conversations) is "order" in the sense of "first order logic", "second order logic"; not in the sense of "first proposition, second proposition" etc.

His claim is that the proposition "This proposition is not provable", formalized as "P equivalent to P is not provable" is not well formed in a typed logic, as "P"'s type is first-order, while "P is not provable"'s type is second-order. Therefore, his claim is that the proposition is simply not well-typed and therefore not interesting. Godel's proofs were discussing an untyped logic, but according to Hewitt that is not an accurate representation of mathematics.

I don't think anyone in the space agrees with him, though, as far as I could tell from some cursory reading.

Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by ProfHewitt on Saturday June 19, 2021 @01:58PM (#27562714)
[Gödel 1931] was for a system for the foundations of

mathematics with orders on propositions.

The [Gödel 1931] proposition I'mUnprovable is certainly of

historical interest and may perhaps be of philosophical

interest.

However, including the proposition I'mUnprovable in

foundations makes the foundations inconsistent.

Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by ProfHewitt on Thursday June 17, 2021 @02:18PM (#27542679)
[Gödel 1931] encoded the characters of a proposition in its

Gödel number but did not include the order of the proposition.

Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by espadrine on Thursday June 17, 2021 @02:51PM (#27543098)
Could you provide two statements with equal Gödel numbers but distinct proposition orders, and a detail of how you compute the Gödel numbers?
Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by ProfHewitt on Thursday June 17, 2021 @03:57PM (#27543887)
If two propositions have the same characters, then they have the same Gödel numbers.
Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by espadrine on Thursday June 17, 2021 @05:55PM (#27544870)
Could you provide two statements with equal Gödel numbers and the same characters in different orders, and a detail of how you compute the Gödel numbers?
Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by ProfHewitt on Friday June 18, 2021 @07:16PM (#27556073)
If two propositions have the same characters in the same order,

then they have the same Gödel numbers.

Unfortunately, Gödel number of a proposition leaves out the order of the proposition :-(

Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by espadrine on Saturday June 19, 2021 @03:27PM (#27563616)
If two statements have the same characters in the same order, how are they not the same statement? And why would that make Gödel’s statement invalid in Principia Mathematica?
Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by ProfHewitt on Saturday June 19, 2021 @04:24PM (#27564120)
There might be two propositions of different orders that have the

same characters in the same order.

Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by deadbeef57 on Thursday June 17, 2021 @02:04PM (#27542514)
I know of several computer verified proofs of the incompleteness theorem. See entry 6 of https://www.cs.ru.nl/~freek/100/ for a small catalogue. How does this relate to your objection? Are there bugs in the verifiers? Or did people verify the wrong theorem statement?
Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by ProfHewitt on Thursday June 17, 2021 @02:34PM (#27542869)
Proofs forgot to include order of proposition in its Gödel number.
Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by deadbeef57 on Thursday June 17, 2021 @04:06PM (#27543986)
So you say that the computer verified proofs of the incompleteness theorem of verifying the wrong theorem? Because there can't be bugs in a computer verified proof.

(Of course there can theoretically be bugs in a computer verified proof. If there are bugs in the verifier. But if 4 independent proof assistants verify a proof of a theorem, this is extremely unlikely.)

Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by ProfHewitt on Friday June 18, 2021 @07:21PM (#27556110)
A proof is only as good as definitions and axioms used in the proof.

All of the computer-verified proofs of existence of [Gödel

1931] proposition I'mUnprovable left out the order of

proposition in its Gödel number :-(

Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by myWindoonn on Friday June 18, 2021 @11:24AM (#27551330)
Suppose that Turing is wrong. Then Turing gave an algorithm which should defeat Rice's Theorem. Therefore, I may simply ask, to Hewitt: Could you please write up a short program in a popular Turing-complete programming language which proves or disproves Goldbach's Conjecture? It should be trivial!

Of course, on actual computers, Turing's result applies, Rice's Theorem manifests, and such a program will likely run indefinitely, until we get bored and give up.

The point that Hewitt has made in another thread is typical misdirection. See, it doesn't matter which order of logic we're talking about; in general, we have results for higher order logic, all the way up to Lawvere's fixed-point theorem for any Cartesian closed category. To fight this, Hewitt has to disclaim the entirety of 20th-century mathematics. (At least he's internally consistent -- he does deny modern maths!)

Sad fact is that, ever since 1976 (http://www.laputan.org/pub/papers/aim-353.pdf) folks have recognized that Hewitt's claims about the foundations of computation are not just wrong, but flamebait. But he never had the humility to learn from his mistakes.

Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by alisonkisk on Thursday June 17, 2021 @10:41AM (#27540081)
What's wrong with ActorScript? Does it have some kind of infinite-size features?

More interesting facts:

His Twitter account has been relatively recently deleted

https://mobile.twitter.com/drcarlhewitt/status/3972794314824...

And his PhD advisor was Seymour Papert.

Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by ProfHewitt on Thursday June 17, 2021 @10:51AM (#27540189)
Twitter account is @ProfCarlHewitt and blog is

https://professorhewitt.blogspot.com/

See following for a simple ActorScript program that cannot be

implemented using a Nondeterministic Turing Machine:

https://papers.ssrn.com/abstract=3603021

Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by mcguire on Thursday June 17, 2021 @02:29PM (#27542803)
"...his ActorScript can't be implemented on real machines."

I think I understand why, but could you provide some more details?

Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by myWindoonn on Friday June 18, 2021 @11:27AM (#27551368)
Loosely, because ActorScript requires some sort of genuine non-determinism where an actor explores multiple states simultaneously, we need some sort of magic non-deterministic computer. A quantum computer isn't enough; simulating an ActorScript program is NP-complete.

Maybe there can be physical machines which run ActorScript, but I would expect them to come with new laws of physics, and also I think that there are probably more comfortable programming languages. We already have https://en.wikipedia.org/wiki/Constraint_Handling_Rules for example.

Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by mcguire on Friday June 18, 2021 @04:38PM (#27554761)
Thanks!
Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by joelbluminator on Thursday June 17, 2021 @09:15AM (#27539238)
Maybe he should try writing it in Elixir instead of ActorScript?
Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by weatherlight on Thursday June 17, 2021 @11:37AM (#27540775)
Hewitt argues that erlang/elixir/beam isn't the actor model because of how Erlang processes receive/process messages

more here: https://www.erlang-solutions.com/blog/lets-talkconcurrency-p... and here: https://codesync.global/media/almost-actors-comparing-pony-l...

Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by ProfHewitt on Thursday June 17, 2021 @11:50AM (#27540947)
Of course, Erlang can be accurately modeled using the theory of Actors.

See discussion in Related Work section of the following article:

https://papers.ssrn.com/abstract=3603021

Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by weatherlight on Wednesday June 30, 2021 @09:16PM (#27695366)
Prof. Hewitt himself!
Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by ProfHewitt on Thursday June 17, 2021 @09:41AM (#27539450)
myWindoonn: Do you have anything of actual substance to

contribute to the the discussion?

Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by myWindoonn on Friday June 18, 2021 @11:17AM (#27551244)
We found http://www.laputan.org/pub/papers/aim-353.pdf the other day. How's it feel to know that folks have been calling you out on your incorrectness since the 1970s?
Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by ProfHewitt on Thursday June 17, 2021 @09:53AM (#27539565)
A fundamental problem with Wikipedia is that it doesn't have

proper accountability for material that it publishes.

Furthermore, Wikipedia is heavily censored by an anonymous group.

See [von Plato 2018] on how Gödel deceived von Neumann in

developing one of his fundamental proofs in [Gödel 1931].

Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by saurik on Thursday June 17, 2021 @03:36PM (#27543657)
That wikipedia article is edit-locked and if you look at its history it is, in fact, hilarious.
Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by ProfHewitt on Friday June 18, 2021 @12:40PM (#27552212)
Why do you find Wikipedia censorship hilarious?
Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by saurik on Friday June 18, 2021 @01:39PM (#27552832)
Because it is? It isn't quite "ridiculous", as it is somewhat more amusing than that. It certainly isn't "funny", FWIW, as I have absolutely no positive connotations with it... "hilarious" feels like the correct term.
Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by ProfHewitt on Friday June 18, 2021 @03:39PM (#27554075)
Hilarious means "extremely amusing", which is your position on censorship?
Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by koheripbal on Friday June 18, 2021 @06:28PM (#27555687)
I agree... while the video is great - it does have a pretty big hole there.
Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by gpderetta on Thursday June 17, 2021 @06:33AM (#27538138)
for those that haven't clicked through, the MIT professor is none other than Carl Hewitt of actor model fame.

I should post the wiki link so that we can have the whole discussion again :)

Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by Workaccount2 on Thursday June 17, 2021 @10:08AM (#27539729)
>Carl Hewitt of actor model fame

I'll admit that threw me for a loop for a second.

Re:1931: Kurt Gödel shows limits of math, logic, computing, AI by gpderetta on Monday June 21, 2021 @12:15PM (#27580638)
:) Sorry, I guess it ended up being some sort of https://en.wikipedia.org/wiki/Garden-path_sentence