Unsolved Problems

Tim Roberts maintains the website http://www.unsolvedproblems.org/ in which he presents unsolved problems from mathematics, mostly conjectures that yet lack a formal proof. While working on these problems is fun, it may be useful to know that some problems might be unsolvable, so they are not worth the effort trying to solve them.

By means of formal logic we can show that some problems are probably unsolvable. If we can reformulate a statement to be of the type "there does not exist any n for which ...", it is probably unprovable. Examples:

Goldbach Conjecture

The Goldbach Conjecture states that every even number greater than 2 is the sum of two primes. A number is prime if it is divisible only by itself and 1. So, for example, 36 = 17+19.

This is equivalent to: For every integer n greater than 1, there is an integer k so that both n - k and n + k are prime numbers.

Employing the existential quantifier only, we can reformulate this to: There does not exist any integer n greater than 1 for which there does not exist an integer k so that both n - k and n + k are prime numbers. This can, if it is a false statement, easily be disproven, but it is probably impossible to prove.

Twin Primes Conjecture

The twin primes conjecture states that there are an infinite number of pairs of primes of the form 2n-1, 2n+1. That is, they differ by 2; for example, 41 and 43.

This is equivalent to: There does not exist any integer k which is larger than any pair of primes of the form 2n-1, 2n+1. "There does not exist any"... probably impossible to prove.

Collatz Conjecture

Take any positive integer: if the number is even, divide it by two; if the number is odd, triple it and add one (for example, if this operation is performed on 26, the result is 13; if it is performed on 5, the result is 16). Perform this operation repeatedly, beginning with any positive integer, and taking the result at each step as the input at the next.

For example, starting at 11, the sequence goes 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.

The Collatz conjecture is: this process will eventually reach the number 1, regardless of which positive integer is chosen initially.

This is equivalent to: There does not exist any integer n for which the given algorithm does not result in the number 1. Probably impossible to prove!

However, Fermat’s Last Theorem is also a conjecture of the "there does not exist any n for which ..." type, which should render it unprovable, but it has been proven.

So I do not claim that the problems which seem to be impossible to prove are unprovable indeed, but probably they are.

Claus Volko

Comments

Post a Comment

Popular posts from this blog

A Proof that Every Grammar for English has Self-Embedding to an Unbounded Depth

Authors: Daniel Pohl, Iakovos Koukas, Noam Chomsky Introduction The distinction between competence and performance has played a foundational role in the philosophy of linguistics. Competence is a grasp of the structural properties of all the sentences of a language. Performance involves actual real-time use and may diverge from the underlying competence. Idealizing away from psycholinguistically relevant factors like limits on memory and processing plays a significant role in various essential debates within the field of linguistics. Perhaps the most central and famous is the issue of whether English is a finite-state language. This article provides a proof of the relevant theorem, originally from Chomsky 1959. The claim that any finite-state automaton does not accept English is supported by showing that every grammar for English has self-embedding to an unbounded depth. Self-Embedding The economical production forms for context-free languages, especially the Chomsky normal-for
Read more

Symbiont Conversion Theory

Abstract Symbiont Conversion Theory is a new scientific theory, summarizing and generalizing efforts that have been made by various researchers in the past years; it could even be perceived as a new scientific paradigm. This theory states that microorganisms and cells which are commonly considered to display parasitic behaviour can be "educated" and transformed into symbionts. This is not just a hypothesis but a theory since there is already evidence that proves that this is possible. The primary motivation for developing this theory is the failure of classical approaches to therapy of cancer and infectious diseases that follow the paradigm "destroy and kill". It is common knowledge about medical doctors that chemotherapy and radiation therapy have detrimental side effects on healthy, functional tissue, and also that antibiotics can harm benevolent cells. These negative side effects can possibly be avoided by the new approach of treating parasitic diseases by conver
Read more

Optimal IQ: A Speculative Model

Image
How we profit from IQ is frequently talked about in IQ societies. And the foregone conclusion: the higher the better . However, turns out there’s a cost associated with higher IQ, one put forth in a recent paper[1] indicating the good of high intelligence; more opportunities, higher self–awareness, etc and the more elusive bad or dark side to higher IQ; imbalances (mental and physical), debilitation, etc. In other words, there is a cost associated with IQ increase beyond some as yet, unknown value. Now, optimality, as we all know, is not necessarily being on top of the heap or at a maximum. Take an aspirin, it will get rid of a headache. Take a bottle of aspirin and you’ll be in the ER getting your stomach pumped. Even money— turns out you don’t want to make too much —has an optimal value being about $95,000.00 US dollars per year in the long run, that is, if one wants to be happy— optimally of course. Too, to determine optimality, as we all have learned, requires in the simplest sense
Read more