12
$\begingroup$

I am aware this is in the gray area of “story question or world question” but I think it is at least mainly world based.

So in this reality set in the far future, somehow a certain math problem has been found to be the solution to all problems. How? Doesn’t matter, but everyone agrees that this is what needs to be solved.

So obviously everyone strives to solve this. Nobody tries to solve it by hand though. Everyone uses some sort of computer, that is until stereotypical_main_character comes along and figures it out by doing it by hand.

The problem is that I cannot think of any logical way that a computer when given enough time couldn’t solve a problem but a person could. Perhaps an alternative mathematical convention would be needed? Maybe something similar to the creation of imaginary numbers would have to happen. I have no idea about anything about how this problem would have to work, I’m pretty bad at math.

Do note I am not asking for you to attempt to create such a math problem,(although I suppose you could) just if it is possible to exist in reasonable conditions.

Improve this question
$\endgroup$
14
  • 3
    $\begingroup$ What kind of sci-fi computer are we talking about? The dumb "can only follow rules" kind or the AI "smarter and more creative than any human" kind? $\endgroup$
    – GrumpyYoungMan
    Dec 31, 2021 at 4:59
  • 1
    $\begingroup$ @GrumpyYoungMan the same computers we have now, only greatly amplified in processing power, storage, memory, etc. $\endgroup$
    – Topcode
    Dec 31, 2021 at 5:03
  • 2
    $\begingroup$ "the same computers we have now, only greatly amplified in processing power, storage, memory, etc." Then it is not what we have now $\endgroup$
    – L.Dutch ♦
    Dec 31, 2021 at 5:07
  • 1
    $\begingroup$ @Topcode That's only true if you assume that you can't simulate human thought on a sufficiently advanced computer. $\endgroup$
    – sphennings
    Dec 31, 2021 at 5:42
  • 4
    $\begingroup$ I speak of none but the computer that is to come after me. A computer whose merest operational parameters I am not worthy to calculate! Yet I will design it for you! A computer which can calculate the Answer to the Ultimate Question, A computer of such infinite and subtle complexity that organic life itself shall form part of its operational matrix. $\endgroup$
    – Trioxidane
    Dec 31, 2021 at 8:58

12 Answers 12

Reset to default
18
$\begingroup$

When is a Math Problem not a Math Problem?

A riddle who's answer looks like math but isn't. There seems to be no answer. The Gordian knot was a giant knot with the ends buried in the middle in the temple of Gordium, and anyone who could unravel the knot was supposed to be destined to rule all of Greece. Clever guys came and went trying to solve the knot. Alexander the Great came and hacked it to pieces with his sword. Problem solved. Not this exactly, but something on those lines.

Another example of this is the Kobayashi Maru from Star Trek, where the only answer to the problem is to cheat. You go outside computer logic and force a solution only by violating the apparent limits of the problem.

Improve this answer
$\endgroup$
7
  • 4
    $\begingroup$ If the symbols taken for numbers by the computer actually represent other entities (e.g. letters, words) this becomes a cryptography problem, not a math problem. Computers which set out to solve math problems might not question what the symbols in the problem represent. $\endgroup$
    – Willk
    Dec 31, 2021 at 19:45
  • $\begingroup$ While the other answers on this question are good. I like this one the most. Many humans are great at creativity, and this answer uses that well. Only a human could solve this math problem because it isn’t even a math problem at all, and only a human could see that. $\endgroup$
    – Topcode
    Jan 2, 2022 at 4:40
  • 1
    $\begingroup$ not sure if the Gordian Knot is a good example as it was the use of brute strength over mental problem, but I like the Kobayashi Maru analogy. A computer following it predetermine guidelines to solve a problem wont look outside the box to find the solution $\endgroup$
    – Sonvar
    Jan 5, 2022 at 19:50
  • $\begingroup$ @Sonvar: The Gordian knot is still an example of a mental problem. Anybody with a sword could have cut the knot. Only Alexander realised that he should cut the knot! $\endgroup$
    – Joe Bloggs
    Jan 6, 2022 at 10:35
  • $\begingroup$ @JoeBloggs to be honest, the solution of cutting the rope was probably not the initial intent and Alexander probably didnt intent to provide a real solution. He probably did it to enforce his might upon the people, intending only to have a show of force. The fact that his actions solved the problem was probably only an unintended consequences. All we can go on is embellished stories of that time, written by people that lived 100 years after the event $\endgroup$
    – Sonvar
    Jan 6, 2022 at 14:20
12
+100
$\begingroup$

Mathematical Proofs

The most difficult problems in mathematics are mathematical proofs, I would think these qualify as mathematical problems.

Computers are currently very dumb but very fast, even the current AIs (neural networks) are just a kind of smart brute force methods. Creating general-purpose thinking AIs is still completely beyond our capabilities. As you said in your comments, "the same computers we have now, only greatly amplified in processing power, storage, memory, etc.", would make the computers only faster at problem-solving not better.

Hence any problem that cannot be solved today by a computer given enough time is still not solvable by a faster computer.

The mathematical problems that cannot be solved with enough time are problems that include some variant of infinity. One example of such a problem would be the Collatz conjecture. A computer might prove it false by brute force if it finds a loop at some point, but can never prove it true in this way. Proving it true would require a mathematical insight that a computer (nor currently humanity) does not have, regardless of how fast it is.

Basically, computers can solve mathematical problems where there are a clear set of rules to follow. This set of rules might be very large and complicated but must be there. Faster computers only speed up the calculation but do not invent new rules. Inventing and understanding new rules is outside the scope of modern algorithms.

Improve this answer
$\endgroup$
7
  • 9
    $\begingroup$ Are you aware of automated theorem provers? A proof of any mathematical statement (say the Collatz conjecture) can be expressed as a discrete data structure -- a chain of elementary reasoning steps grounded in a small number of axioms. There is no algorithm guaranteed to prove or disprove an arbitrary mathematical statement (because there is no way to know how large the proof or counterexample may be, and the statement might be undecidable), but if there is a proof, it can in principle be eventually found by brute force: Try length-1 proofs, then length-2 proofs, etc. $\endgroup$
    – nanoman
    Dec 31, 2021 at 21:06
  • $\begingroup$ @nanoman: The problem with such provers is that, for interesting statements such as Collatz, they require a completely unreasonable amount of computational resources, and also they fall apart if you give them something independent of the stated axioms, like Goodstein's theorem or the Continuum Hypothesis. $\endgroup$
    – Kevin
    Dec 31, 2021 at 22:37
  • 2
    $\begingroup$ @Kevin Correct, but the question envisions computers "greatly amplified in processing power", and this answer claims that a math statement over an infinite space inherently cannot be proved by a computer "by brute force...regardless of how fast it is". I'm saying that argument is false, even though theorem provers can't currently replace human mathematicians. And a human would also fall apart trying to prove or disprove an undecidable statement. They could try to prove that it's undecidable, but so could a computer, with a formalized metatheory. tl;dr Proving is a search for a finite object. $\endgroup$
    – nanoman
    Dec 31, 2021 at 22:52
  • $\begingroup$ @nanoman I did not know automated theorem provers and sadly haven't had the time to read up on them yet. I just wanted to say this is why I love stack overflow, it is such a nice community sharing knowledge. $\endgroup$
    – D.J. Klomp
    Jan 1, 2022 at 1:36
  • $\begingroup$ @nanoman: There exist statements that do not admit a proof, and also do not admit a metaproof-of-no-proof (within a specific formalized metatheory). This must be the case, because otherwise, you could solve the Halting Problem by (concurrently, with interleaved execution) running the machine, searching for a proof that it doesn't halt, and searching for a metaproof that halting is independent. If a machine does halt, you can always prove that this is the case, so the metaproof will only be found when the machine does not halt. $\endgroup$
    – Kevin
    Jan 2, 2022 at 0:42
1
$\begingroup$

When humans work with geometry often they try to add their intuition to what calculus tells them. There could be a problem based on multidimensional data that people try to solve numerically because they can't picture a manyfold in their minds. But someone tries to plot all the possible projections of the data and keeps all those plots side by side on a wall in his home. Suddenly one day he sees a pattern going through all those projections.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Well this is a tad awkward. Accidental downvote. But I do have some feedback, if you are putting all the possible projections by each other, wouldn’t you always get a pattern, since the data is the same? $\endgroup$
    – Topcode
    Jan 7, 2022 at 1:29
1
$\begingroup$

No, in general.

Kinda yes, to problems which are human related, in specific story based curcumstances.

As of today's neural network uses do show - we can, more or less, make programs and computers work with the same or similar principles as do our brains work, and in essence, it means what a human is capable of then a computer is capable of it too, especially in a sense of problem solving. Sure we are quite a way(or not) away from Asimov robots intelligence, but ....

  • so no, and reasoning is quite similar to D.J. Klomp answer, which is correct, with a proof, if we are interested in knowing - is it possible or not, then correct answer is - no.

On the other hand, it is possible to have very different complexity in finding a solution, because of who or what one is. We can see such things every day - computer vision is still a challenge, but for most people, animals, insects it is not such a big problem. On the other hand - AlphaGo plays go game better than any human on the planet - so there are things which those outperform himans already, and it not (from our standpoint of view) just crunching the numbers (it is but...)

For a human, it is easy to say if something tastes good, because yeah human equipt with predefined neural networks, receptor and all that - basically just because of it being a human, and because field of all those possible answers is created by humans, for humans, and because what humans are - as biological creatures, all that evolution and such.

A computer can be trained to answer what some human will find tasty, but it requires a lot more efforts, as of today, it sure is a high tech. But it can't answer the question what tastes good for that program - because the field of those answers does not exists, because of what the program is. Even for an human level AI it would be meaningless question with nan-answer (it can use it as words in communications with humans, but it just a way to transfer information, making things to react in a way etc)

So questions like - what do you like - will always be simplier to answered by humans than programs, because humans can use themselfs as gauge, as etalon, as master reference, and do not have to make some convoluted estimation metrics.

It goes deeper than that, not just like/dislik but also how, in which way humans can change, evolve, but it is harder to explain. But as easier example of that - classics - what is meaning of life. Humans can define it by their actions and such - meaning they can make self fulfilling prophecy, choose it to be, and anything out of wide range of potencial answers can become the One correct answer. (But such a choice can be predicted, given enough hightech data and all that - kinda)

So there can be some problems with disparity of complexity, is such a difference is enough - it depends on a story, what do they have, and what they do not have.

In general attempt to find such a clear disvision line between - is so old fashion, 70's really. Correct answer is no, but you can easy handwave it to yes in thousands of ways, as an example by degree of development of the means they have and not only that.

Improve this answer
$\endgroup$
1
$\begingroup$

It is almost certainly impossible for a math problem of the type you describe to exist.

The problem isn't about trying to find a math problem that humans can solve but computers can't. There are plenty of such problems even today, recently solved by humans and with no feasible strategy of finding a proof by a computer. In the future, humans will likely always be able to devise new questions which lie just outside the range of what computers of their time can solve.

The problem is your requirement "somehow a certain math problem has been found to be the solution to all problems".

This is like asking for a universal strategy that somehow plays optimally for every board game or computer game that exists or can possibly exist. Or asking for a universal device that functions as a car, a cellphone, a refrigerator, a spaceship, and every other engineered device the human race needs or will ever need. Or a universal medicine that cures all ills and diseases the human body can ever experience.

You don't have to be a doctor to have enough experience to conclude that a universal cure is almost certainly impossible. I can't prove it doesn't exist, but its possibility goes against every piece of experience medical science has ever given us.

It is similar with math. I may not be able to prove it mathematically, but experience shows that searching for some single magic conjecture that solves all other possible mathematical questions sounds wildly divorced from reality.

Improve this answer
$\endgroup$
8
  • $\begingroup$ I think you may have misunderstood the question. $\endgroup$
    – Topcode
    Jan 7, 2022 at 1:22
  • $\begingroup$ You are asking if it "is possible to exist in reasonable conditions". I am pointing out that the properties you demand of this math problem make it almost certainly impossible, independently of computers. I already answered your question about computers as well. $\endgroup$
    – Priska
    Jan 7, 2022 at 16:36
  • $\begingroup$ I again, think you misunderstand the question, that or you have tried to make a frame challenge answer. Either way, your answer doesn’t really do much, the question would work the same without that part. It’s like if I asked you “hey does this floor have water on it, it seems wet” and you say “no it doesn’t have water on it because atoms don’t actually touch each other so nothing has anything on it” you’re answering a question not being asked $\endgroup$
    – Topcode
    Jan 7, 2022 at 16:48
  • $\begingroup$ Are you saying that your whole preamble about some future setting with some super-important math problem is entirely unrelated to your question, and that your actual question is simply asking for just some math problem people can solve and computers can't? That question is easy to answer. It also doesn't have anything to do with worldbuilding. $\endgroup$
    – Priska
    Jan 7, 2022 at 16:52
  • $\begingroup$ At this point I think you barely read the question. $\endgroup$
    – Topcode
    Jan 7, 2022 at 16:55
0
$\begingroup$

Providing a readable mathematical proof for e.g. Pythagoras

Lots of kids do that every day in school, but computers can't.

In case of Pythagoras, a schoolkid could write down a 20 lines basic proof based on a geometrical construct. A simple Pythagoras proof is based upon congruence of triangles: you put an orhogonal line to the other side, then you state angles are equal, so you find 3 congruent triangles. The pupil will put a little drawing that includes the squares, annotates the sides with a b and c, then states that the area of a square is its sides squared, hence a2+b2=c2, QED.

Continuous domain

For a computer, the main issue would be: where to start. What exact construct is appropriate. The computer would have to iterate over all possible intersections, that will take some time..

It will run..

Theory sais computers can generate mathematical proof from axioms.

Theoretically, any mathematical proof can be generated by feeding the computer a set of relevant axioms.

https://en.wikipedia.org/wiki/Automated_theorem_proving

For Pythagoras, a program could be written that proves it.

(to find a proof, you'd have to assume an ideal computer)

A way to circumvent o.m.'s halting problem (for this example, mathematical proof) is assuming an ideal computer: we have a theoretical device, that can perform any convergent iteration in zero time. This device can come up with PI in an arbitrary number of decimals, the result pops up immediately. For any correct mathematical assumption your ideal computer will always come up with a sound proof, if the assertion is true and the set of axioms you feed it is complete.

The real issue: printing the output

Computers have to be programmed to format the output in a suitable way. You'd run into topics of summarizing results using natural language, which computer programmers have not solved yet. A computer can perform any mathematical proof, however it is not known yet, how to transform the result to make it readable/understandable for e.g. teachers in school.

If readability is a requirement, humans will have a huge advantage.. instead of a list of 20 pages we want this,

enter image description here

Improve this answer
$\endgroup$
3
  • $\begingroup$ This answer is beyond wrong. Computers have zero problems formatting mathematical formulae. This is a solved problem, and it has been a solved problem for a long time. The problem has always been providing the computer with the deep knowledge required in order to perform efficiently as an assistant to a research mathematician. Nowadays there are quite a few efforts to compile machine-readable databases of mathematical proofs; for example, look up Metamath, Isabelle, etc. $\endgroup$
    – AlexP
    Dec 31, 2021 at 14:28
  • $\begingroup$ @AlexP a computer is perfectly able to state a formula in a printout, we all know what LaTeX can do. But I have not seen computers generating sound explanations in natural language. That is why I took geometry, schoolkids and Pythagoras as an example. When you require a short mathematical proof like Pythagoras theorem in a school exam, that will require an illustration.. and the explanation. This is a mathematical problem (because it concerns software) which is not solved yet, as far as I know. $\endgroup$
    – Goodies
    Dec 31, 2021 at 14:37
  • $\begingroup$ @AlexP we can agree about the assistant part. Mathematicians will be able to use these tools and decypher the output. I've replaced "mathematicians" by "e.g. teachers in school". Thanks for the feedback. $\endgroup$
    – Goodies
    Dec 31, 2021 at 15:32
0
$\begingroup$

There are infinitely many math problems that a computer can't solve unless a human feeds it "hints" (inputs). If your computer returns the result of 2+2 as 4, it's because it somehow got this information from humans, and this is true for any problem that exists or may come to exist.

Once your main character figured out the solution to the new problem, he'd sure be at an advantage if the computer doesn't know how to solve it, but what's so special about it? Nothing. If I ask a computer to calculate my age without telling it what year I was born, it won't know what to return, and in the meantime I can ask my mom what my age is and she will know, even if I had never passed that information on to her.

My answer to your question is: Any mathematical problem, as long as the computer does not have enough information about the variables of the problem, it will never know how to solve it.

Improve this answer
$\endgroup$
6
  • $\begingroup$ “If your computer returns the result of 2+2 as 4, it's because it somehow got this information from humans” Not really? Computers aren’t programmed case by case, they use generic algorithms. “If I ask a computer to calculate my age without telling it what year I was born, it won't know what to return, and in the meantime I can ask my mom what my age is and she will know” How is this relevant, if you ask any generic human what your age is, just like the computer, they won’t know. And if you tell the computer the same information your mom knows it will solve the problem just the same. $\endgroup$
    – Topcode
    Dec 31, 2021 at 20:37
  • $\begingroup$ @Topcode "And if you tell the computer the same information your mom knows it will solve the problem just the same" Exactly my point, the computer knows absolutely nothing until you teach it. "Computers aren’t programmed case by case" I didn't say that a human specifically taught a computer that the result of 2+2 is 4, I said that the computer knows this is the result because it learned it somehow from humans. The relevance here being: A human knowing how to solve something that a computer does not know is more common than a computer knowing how to solve something that a human can't. $\endgroup$
    – Luna
    Dec 31, 2021 at 21:05
  • $\begingroup$ @Topcode "if you ask any generic human what your age is, just like the computer, they won’t know." He may not know precisely, but he can guess a number that is very close to the correct one based on my physical characteristics (which are nonetheless some sort of input), a computer cannot get solutions from nothing, just like we also can't, but if we're talking about computers that use the same principle as today's computers, they still require us humans to teach them what we know. $\endgroup$
    – Luna
    Dec 31, 2021 at 21:09
  • $\begingroup$ Your answer doenst answer the question, input is a separate thing from a problem. If you don’t give a human any input, just like a computer it won’t do anything. Input is essentially an irrelevant point since it is specific to neither the human nor computer $\endgroup$
    – Topcode
    Jan 1, 2022 at 0:00
  • $\begingroup$ @Topcode I'm just assuming you're trying to make the main character look special or something because he's able to do what programmers do on a daily basis: Create a solution to a problem before handing it over to a computer. My answer to your question is: Any mathematical problem, as long as the computer does not have enough information about the variables of the problem, it will never know how to solve it. $\endgroup$
    – Luna
    Jan 1, 2022 at 1:41
0
$\begingroup$

In your world, the brain cannot be modeled by a Turing Machine, that is: The way computer works, no program would be able to precisely imitate and reproduce the working of the brain, no matter how complex the simulation is. As such, the brain is able to do things that no Turing Machine (and thus no computers) would be able to achieve. Mathematically, there are models for automaton that can compute more things than Turing Machine, but the "trick", at least for the known ones, is that they involve infinity in the way they work and as such cannot be physically made.

I remember reading some years ago that it wasn't known whether or not there existed mathematical models of computation that were both realizable and more computationally powerful than Turing machines (as in "can do things that Turing machines can't"). Obviously, if one such model was found we would know already, but it may still not have been proven that there aren't.

Perhaps you could use this as a premise for your universe: "Such a model exist, and in fact, the brain is a realization of it.".

However know that if such a physically realizable model existed, it would have implications regarding our reality, as it would mean reality and our laws of physics are too complex to be perfectly simulated by a computer (otherwise we'd have a contradiction: you would be able to realize this more powerful model inside a simulation, meaning that a computer would be able to compute stuff that only this more powerful model should be able to).

Improve this answer
$\endgroup$
-1
$\begingroup$

The human discovers a new axiom

To horribly oversimplify how mathematicians work, a base set of rules/operations are chosen which are considered to need no proof of correctness and and those rules are combined and manipulated to prove other more complex rules. Every mathematical structure built in this fashion is provably true since the logical steps that constructed it can be traced back down to the original base set of rules. This base set of rules/operations are referred to as axioms and a familiar example from high school geometry are Euclid's geometric axioms. "Dumb" computers are very good at following and manipulating rules; in a sense that's all that they do. Modern computer symbolic algebra systems like Mathematica are examples of computers applying mathematical rules to solve problems and perhaps in the future, computers are even more efficient at grinding through the theorems to create new ones.

However, what the computer cannot do is question the rules. While extremely improbable, for fictional purposes, what if one of the base axioms turned out to be incorrect? Nothing proves that they are true; they are assumptions (albeit well-chosen and reasonable ones) and there have been disagreements and suggestions for modifications to these axioms in the past.

So, let's say your character is looking at the output of all this software and realizes that there is a contradiction that shows one of these axioms wasn't valid at all and could be replaced with a better one. This leads to new mathematics with different results for whatever esoteric problem that they're trying to solve.

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ I don’t think this answers the question. Once the new axiom is discovered, the computer can then solve those kinds of problems. The question seems to want a type of problem that can only be regularly solved by people, not computers. $\endgroup$
    – SRM
    Dec 31, 2021 at 6:44
  • 3
    $\begingroup$ Axioms are not something which can be discovered. Axioms are assumed. Moreover, there is nothing inherently better or worse about working with one set of axioms over working with another set. You can admit the axiom of choice, or you can reject it, and both options lead to perfectly valid mathematics, just different. $\endgroup$
    – AlexP
    Dec 31, 2021 at 8:09
  • 1
    $\begingroup$ @SRM You are thinking of "math problem" in a very narrow sense, similar to math problems in a school textbooks, and that is probably not what the querent wants based on the wording of the question. Discovery of mathematical techniques make previously intractable problems tractable; an example is the development of the theory of relativity in physics which depended on the development of tensor calculus and Riemannian geometry beforehand. $\endgroup$
    – GrumpyYoungMan
    Dec 31, 2021 at 8:20
  • $\begingroup$ @AlexP While it's true that any non-contradictory set of axioms can produce different but valid mathematics, the querent wants to solve something of practical use ("solution to all problems") so presumably choosing axioms that yield mathematics that better describe what occurs in the real world might provide new insights in physics. Note that I'm not saying this is practical or realistic but it's the least obviously implausible way to handwave what the querent is trying to achieve in their fiction. $\endgroup$
    – GrumpyYoungMan
    Dec 31, 2021 at 8:26
  • $\begingroup$ @grumpy Sure, but once the new technique is discovered, what prevents a computer from applying it? Even theorem proving and discovery are open to computers (see “ACL2” programming language). $\endgroup$
    – SRM
    Dec 31, 2021 at 14:30
-2
$\begingroup$

No, but you might have a verification problem

My second answer but on a very different thought line and quite opposite to my other answer so I posted it as a new answer.

There is the Infinite monkey theorem, saying that a monkey hitting keys on a typewriter given enough time will write the work of Shakespeare.

Say your character is brilliant and can write the proof to the not yet determined problem on one page. A fast enough computer can create all possible combinations of characters on a single page. As such the solution to the mathematical problem will be included in the created combinations. (If your dealing with mathematical symbols and images one can simply replace characters with pixels to achieve the same result).

So our current computer, given enough time, can solve any solvable mathematical problem by just brute force creating all possible combinations on a piece of paper.

What might be the hard part is recognizing the solution to the mathematical problem from all the junk of the other combinations the computer has created.

Improve this answer
$\endgroup$
3
  • $\begingroup$ "A fast enough computer can create all possible combinations of characters on a single page": no it cannot. There are hard fundamental limits to the speed of computation. Enumerating all numbers from $1$ to $95^{2600}$ is not feasible within the life span of the universe. (There are 95 printable ASCII characters, 65 characters per lines, 40 lines per page.) (That's why ciphers such as AES-256 are considered secure in the absence of a major breakthrough in cryptanalysis. Brute forcing $2^{256}$ combinations is considered infeasible.) $\endgroup$
    – AlexP
    Dec 31, 2021 at 14:18
  • $\begingroup$ I know, but the question was given enough time, nowhere was a limitation of the time of the universe specified. So in principle it is possible, I did not say it was feasible. $\endgroup$
    – D.J. Klomp
    Dec 31, 2021 at 15:09
  • $\begingroup$ With infinite monkeys, my conjecture is that on the average, the index for the starting position of a correct answer will be just as long as the answer itself (on the average, and assuming the index uses the full typewriter character set). $\endgroup$
    – toolforger
    Dec 31, 2021 at 16:59
-3
$\begingroup$

The Halting Problem and related issues.

Computer scientists proved almost a century ago that no computer program can determine if an arbitrary program is correct, or even if it will ever come to a finish. Yet humans have been able to prove the correctness or incorrectness of many different programs. Their line of reasoning could be added to the 'rule set' of a program-proving program afterwards, but not in advance.

Of course there are problems which humans cannot solve, either. NP-Completeness is a classic example.

Improve this answer
$\endgroup$
6
  • $\begingroup$ "Their line of reasoning could be added to the 'rule set' of a program-proving program afterwards, but not in advance": really? Citation needed. $\endgroup$
    – AlexP
    Dec 31, 2021 at 8:10
  • $\begingroup$ @AlexP, I can usually explain my reasoning after I solved such a problem, but not before I ever see it. $\endgroup$
    – o.m.
    Dec 31, 2021 at 8:12
  • 4
    $\begingroup$ The undecidability of the halting problem only means that there is no single algorithm that can decide whether every algorithm halts, making absolutely no mistakes ever. For example, given an algorithm that searches for a counterexample to the Collatz conjecture, the halting algorithm has to prove or disprove the Collatz conjecture to determine whether it halts. There is no reason to believe that humans are any better than computers at this. $\endgroup$
    – benrg
    Dec 31, 2021 at 8:13
  • $\begingroup$ @benrg, that's a better point than AlexP made. I took university courses on that decades ago, when brainstorming students could solve assignments that would have stymied early programs. $\endgroup$
    – o.m.
    Dec 31, 2021 at 9:01
  • $\begingroup$ Imagine you write a program that detects another program that can halt and return bol=true and continue checking... see the problem here what if it check itself ;D $\endgroup$
    – user6760
    Dec 31, 2021 at 10:02
-3
$\begingroup$

Perhaps it turns out that there are uncomputable problems which humans can nevertheless solve - maybe humans have souls, or something, and their souls happen to implicitly have access to a halting oracle under certain conditions (and this manifests as "intuition" to the human, who of course can't explain what they're doing because that would be writing down an algorithm, which is forbidden by hypothesis!).

Improve this answer
$\endgroup$
7
  • $\begingroup$ This could work on some sort of situation, however it doesn’t work as far as science based worlds work. $\endgroup$
    – Topcode
    Jan 2, 2022 at 4:37
  • $\begingroup$ I mean, it's not universally agreed upon that Turing machines are human-complete, nor is it universally agreed upon even by physicists that humans lack souls. You're building a world, not a textbook. $\endgroup$
    – Patrick Stevens
    Jan 2, 2022 at 9:39
  • $\begingroup$ Oddly enough, Topcode, you seem to think in your comments on other answers that there is something special and magic about human thought, and yet in your comment on this answer that there is not. $\endgroup$
    – Patrick Stevens
    Jan 2, 2022 at 9:42
  • $\begingroup$ Where exactly did I state that magic was involved? $\endgroup$
    – Topcode
    Jan 2, 2022 at 15:59
  • $\begingroup$ @Topcode > Only a human could solve this math problem because it isn’t even a math problem at all, and only a human could see that. (as if automated classification were simply impossible - which was true twenty years ago, but is not now). $\endgroup$
    – Patrick Stevens
    Jan 2, 2022 at 16:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .