Skip to main content
MathOverflow

Return to Answer

http -> https (the question has been bumped anyway)
Source Link
Martin Sleziak
Martin Sleziak
  • 4.7k
  • 4
  • 35
  • 40

For your "challenge" question, note that it is extremely hard to construct examples of problems of degree strictly less than the halting problem. In fact this was a question open for some years under the name of Post's problemPost's problem. It was finally solved by the invention of the "finite injury method" which gave many examples of such problems. However I do not know of any naturally formulated problem with degree strictly less than the halting problem.

For your "challenge" question, note that it is extremely hard to construct examples of problems of degree strictly less than the halting problem. In fact this was a question open for some years under the name of Post's problem. It was finally solved by the invention of the "finite injury method" which gave many examples of such problems. However I do not know of any naturally formulated problem with degree strictly less than the halting problem.

For your "challenge" question, note that it is extremely hard to construct examples of problems of degree strictly less than the halting problem. In fact this was a question open for some years under the name of Post's problem. It was finally solved by the invention of the "finite injury method" which gave many examples of such problems. However I do not know of any naturally formulated problem with degree strictly less than the halting problem.

Post Made Community Wiki
Source Link
Cody
Cody
  • 1
  • 1
  • 3

For your "challenge" question, note that it is extremely hard to construct examples of problems of degree strictly less than the halting problem. In fact this was a question open for some years under the name of Post's problem. It was finally solved by the invention of the "finite injury method" which gave many examples of such problems. However I do not know of any naturally formulated problem with degree strictly less than the halting problem.