News for hackers. Stuff that matters.
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.