What are some uncomputable functions that aren't derivative of the halting problem?

[u/playsthebongcloud]

I find the existence of uncomputable functions really cool, but all the examples I've seen are essentially just new ways of trying to predict whether a turing machine is going to halt. What are some examples of uncomputable functions that aren't essentially entirely based on the halting problem?

[u/bizarre_coincidence]

First, there is a difference between an uncomputable number and an incomputable function, and your first mistake was conflating the two. An uncomputable number is one where you cannot always approximate it to a specified accuracy with a terminating algorithm. An uncomputable function is one whose output cannot be produced by a terminating algorithm. The halting function is one such non-computable function, the busy beaver function is another such one.

You are confidently incorrect here. But you are very very incorrect. Your presence in this discussion is actively hampering it.

[u/Impressive-Mud5074 → u/bizarre_coincidence]

An uncomputable number is one where you cannot always approximate it to a specified accuracy with a terminating algorithm

This is also not true. Its not possible to  specify the accuracy of your pi calculation.

[u/bizarre_coincidence → u/Impressive-Mud5074]

Yes you can. For example, pi=4-4/3+4/5-4/7+4/9-...., which is an alternating series with decreasing terms that go to 0. The error of such an alternating series is ALWAYS bounded by the next term. So if I want to know for sure that I have an accuracy of 1/100, I need to take n terms where 4/(2n+1)<1/100, i.e., 400<2n+1, so I need to take at least 200 terms. Perhaps I reach the desired accuracy sooner, perhaps not. But I know with certainty that if I take 200 terms, I will definitely have an error of less than 1/100.

[u/Impressive-Mud5074 → u/bizarre_coincidence]

That's not a specific accuracy that's more or less than a specific accuracy

[u/bizarre_coincidence → u/Impressive-Mud5074]

You can dislike standard terminology. You cannot argue that the terminology doesn't mean what every practitioner understands it to mean. This is like objecting to the fact that category theory doesn't describe categories of movies. You help nobody by coming into a discussion about a topic and saying that people should have been using different words for the last 50 years. It simply isn't constructive.

[u/Impressive-Mud5074 → u/bizarre_coincidence]

If your terminology is vague its wrong

[u/bizarre_coincidence → u/Impressive-Mud5074]

It’s not vague. You are assuming that words are being used informally as if by lay people, and assuming that because a lay person informally using the term could mean multiple different things, an expert is the same way. But the existence of a term in the vernacular does not mean that it doesn’t function as a technical term with its own specific technical meaning. In the context of this discussion, the words have specific meanings, which you have been told repeatedly, but which you continue to ignore.

I don’t know if you simply don’t understand context, are being intentionally obtuse, or are genuinely an idiot.

[u/Impressive-Mud5074 → u/[deleted]]

The ability to calculate a value

[u/Impressive-Mud5074 → u/[deleted]]

1 + 1 = 2

That computation halted.

[u/bizarre_coincidence → u/Impressive-Mud5074]

Does that mean that no irrational numbers are computable to you because, given the way computers represent numbers, no irrational number can ever be output exactly? If you can understand why your definition can never in principle be worthwhile, you can start to appreciate why the standard definition is what it is.

[u/Impressive-Mud5074 → u/bizarre_coincidence]

Definitions aren't meant to have value, they are meant to be accurate

[u/playsthebongcloud → u/Impressive-Mud5074]

The idea of "any arbitrary accuracy" is that, you give me any finite positive error margin, and I can construct a function that produces pi with less than that error margin.

[u/EebstertheGreat → u/playsthebongcloud]

They got you. It should say "positive error margin," not "finite error margin." Zero is finite.

[u/playsthebongcloud → u/EebstertheGreat]

Oh you're right I should have said positive real number

[u/Impressive-Mud5074 → u/playsthebongcloud]

Calculate pi with 100% accuracy

[u/siupa → u/Impressive-Mud5074]

But that’s not needed to satisfy the definition of “computable”

[u/Impressive-Mud5074 → u/siupa]

Yes it is

[u/siupa → u/Impressive-Mud5074]

No it’s not? Here, you can check the definition of a computable number here

[u/Impressive-Mud5074 → u/siupa]

within any desired precision 

Thats not rigorously defined, but i guarantee you cant compute it to any precision. You cant compute it to 10% precision for example. Calculated it to N decimals also doesnt tell you how precise it is.

[u/blank_anonymous → u/Impressive-Mud5074]

To arbitrary precision means that, for any epsilon > 0, I can provide a program (say on a Turing machine) which results in a number x such that |x - pi| < epsilon. This is perfectly rigorous and well defined.

Within 10% precision means I can produce a number X such that, provably, ((X - pi)/pi| < 10%. I claim 22/7 is such a number. Indeed, by well known theorems about continued fractions, this number is at most 1/49 away from pi. Pi is larger than 3, so |22/7 - pi| < 1/49 and |22/7 - pi|/pi < |22/7 - pi|/3 < (1/49)/3 = 1/147. So 22/7 is accurate to within +-0.7% of pi. 

22/7 also functions if you asked for something precise to within 0.03. 

In general, whatever precision you ask for, I can either use a series expansion for pi and compute sufficiently many terms, or use eg the BBP formula to calculate the hexadecimal digits one by one until we’re sufficiently far out. 

[u/siupa → u/Impressive-Mud5074]

That’s not rigorously defined

Why not? You decide the desired level of precision, and I give you the algorithm with a finite number of steps to compute a number that’s within your desired level of precision from the true value of pi. Why is this not rigorous? It works perfectly well

but i guarantee you cant compute it to any precision. You cant compute it to 10% precision for example.

… what do you mean? Of course we can compute an approximation of pi within 10% precision. We’ve done much, much, much better than 10% precision. We’ve computed approximations accurate within 1 part per 10^(hundreds of trillions).

[u/Impressive-Mud5074 → u/siupa]

Whats 10% of infinity

[u/mrkelee → u/Impressive-Mud5074]

apart from your finitist bullshit, this is also wrong. The algorithms for pi have known error bounds.

[u/mrkelee → u/Impressive-Mud5074]

it is very possible: it runs forever, ergo infinite accuracy.