>During the first half of the twentieth century, mathematicians such as Kurt
G¨odel, Alan Turing, and Alonzo Church discovered that certain basic problems
cannot be solved by computers. One example of this phenomenon is the problem
of determining whether a mathematical statement is true or false. This task
is the bread and butter of mathematicians. It seems like a natural for solution
by computer because it lies strictly within the realm of mathematics. But no
computer algorithm can perform this task.
Is this true?
During the first half of the twentieth century, mathematicians such as Kurt
David Bailey
Ryan Ortiz
Yes, and if you're interested in this here's a set of lectures that explain exactly these kinds of problems that can't be solved by computation
Lecture one, talks about this very same thing.
Kevin Sullivan
Does this fall under the P versus NP problem?
Angel Gonzalez
Oops, here is the streaming version but you should download these in case they disappear scs.hosted.panopto.com
Gabriel Bell
Thanks, will check them out. But, pardon the inexperience, how do we even accept true or false in programming, why doesn't 1 and 0 count as a predicament? What am I missing?
Jack Baker
Yes, i also heard that Noam Chomsky proved that no computer model can prove that 1+1 is really 2, because computers only deal with approximiations due to the IEEE floating point data types, meaning that no computer can even display the number 2, only 1.99999...
Joseph Myers
You've slightly misunderstood what they proved. It's not that computers can't determine the truth of a statement. For example, any computer could determine the truth of "4 == 2 + 2". Computers can even prove theorems. There's actually a lot of effort going into automating mathematical research.
What the mathematicians you mentioned showed was that there's no guarantee that computers (or mathematicians) will be able to determine the truth of *arbitrary* statements (more precisely: with a finite number of computational steps). Basically this means that there will always be some true propositions than cannot be logically proven to be true (by mathematician or machine).
Liam Adams
>To view this content install or enable:
>Adobe Flash Player
Dropped
Jack Powell
>unironically discussing philosophy of math
lad...
Adrian Ramirez
So, the paragraph refers to the integrity of axioms? Is that what the computers cannot determine as 'true' or 'false'?
Nicholas Morris
Just trying to figure out what the theory of computation is about.
Asher Jackson
That's why I posted the download links too It's a Carnagie Mellon course on theoretical computer science math/intro
Jason Martin
You would know all this if you watched the lectures. Some of your questions require a 20 minute presentation by a professor to show you as they are not easy answers since whatever answer I give you will just produce more questions as you don't have the background.
The second and third lecture covers 'truth' by discovering it through propositional calculus, formal axioms ect.
Christopher Bell
Not the integrity of the axioms, but their reach. For any axiomatic system, the set of true propositions in that system is not wholly covered by the set of true propositions that can be logically proved based on the founding axioms.
In the case of computers, there are true equations that cannot be proven to be true with the arithmetic axioms.
Kevin Sanders
Go fuck yourself. Stop pretending to know things you have no clue about, you dirty piece of shit.
David Carter
Computers actually cannot prove that pi is a finite number because it requires 12 years of computation power to solve that problem, and computer scientists aren't very patient
Jaxson Diaz
>In the case of computers, there are true equations that cannot be proven to be true with the arithmetic axioms.
Sorry, this is badly worded. Here's better:
there are true equations that cannot be proven to have solutions with the arithmetic axioms (i.e. can't be solved with the algebra maneuvers you learned in high school).
Jaxon Phillips
>To view this content install or enable: Adobe Flash Player
>*disables umatrix*
>To view this content install or enable: Adobe Flash Player
what
Jace Green
I asked a simple question, you dumb nigger. I don't pretend to know anything, that's why I asked.
Dominic Lee
Hilbert's 10th problem to be exact, which he added in 1928 to ask "Is there a finite procedure to determine the validity of a given logical expression?" meaning a Betrand Russell type expression such as "In this set, there exists A such that..".
Finite procedure meaning, an algorithm. This was proven no by Church-Turing and the rest of the lectures in that series show you exactly why it was proven no and other problems that have no computational solution outside of approximations such as Max Cut.
Mason Anderson
It's related but since it's an undecided problem it isn't considered NP-complete (being both NP plus NP-hard). cs.stackexchange.com
This explains how the definition of NP is that it consists of all problems that are decidable (not just verifiable) in polynomial time and Hilbert's 10th question is undecided
Of course all these terms in that answer would make sense if you saw all the lectures. You really only need high school algebra to understand it.