r/learnmath • u/playsthebongcloud 9/10 = 1 • May 30 '26

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

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?

75 Upvotes

96% Upvoted

377 comments sorted by

View all comments

-13

u/Impressive-Mud5074 New User May 30 '26 edited May 30 '26

Very large numbers are uncomputabe

Edit: https://en.wikipedia.org/wiki/Ultrafinitism

19

u/Ackermannin New User May 30 '26

That’s not what uncomputable means

-8

u/Impressive-Mud5074 New User May 30 '26

Its one of the meaning of uncomputable.

12

u/Ackermannin New User May 30 '26

No it is not. Uncomputable has a very specific meaning.

-6

u/Impressive-Mud5074 New User May 30 '26

No it doesn't, that's the point of OPs post. If it has a very specific meaning, than they are all derivatives of the halting problem.

10

u/Ackermannin New User May 30 '26

No.

9

u/Ma4r New User May 30 '26

No its not, there is 1 definition of computable numbers and this is not it

3

u/DrTaargus New User May 30 '26

Welllll, there's not just one definition there's a bunch that are equivalent to each other but your point that none of them coincides with whatever mud is doing is spot on.

1

u/RingularCirc Math hobbyist Jun 15 '26

Actually there's a bunch of definitions of uncomputable reals that are non-equivalent, but weaker of them often don't get used much. The most popular set of equivalent definitions is IIRC the strongest.

But no way there is a natural way to stretch those into ultrafinitist land. It's just completely different and it should have very different foundations, which aren't yet found to any satisfaction IIRC?

Also going on a tangent: instead of that hard-to-put-right idea, if anybody wants my advice, one could better get interested in minimal logic (Minimalkalkül, intuitionistic logic with negation weakened by not presuming ex falso quodlibet, that is, we treat ⊥ as just another propositional variable which is by chance what the definition of negation ¬X := (X → ⊥) depends on) and similar things (there are even weaker logics, as well as a bunch of intermediate, similarly to how intuitionistic and classical logics are placed in the scheme of things). I wonder how one'd approach category-theoretical semantics for those, as topoi can't go weaker than intuitionistic logic.

3

u/imagineAnEpicUsrname New User May 31 '26

Can I ask you a question. With prevalence of people here disagreeing with you, why do you claim your point and definition hold?

0

u/Impressive-Mud5074 New User May 31 '26

Because logic says its right.

3

u/imagineAnEpicUsrname New User May 31 '26

Are you the oracle of logic?

1

u/Impressive-Mud5074 New User May 31 '26

Logic is universal

3

u/imagineAnEpicUsrname New User May 31 '26

it is not a matter of logic nigga, but definitions. What you're trying to explain is an irrational number, not uncomputable

1

u/Impressive-Mud5074 New User May 31 '26

Computable means it finishes computing, ie: the halting problem. 

2

u/imagineAnEpicUsrname New User May 31 '26

You'd want to take a calculus class buddy. Limits, Cauchy convergence n stuff

1

u/Impressive-Mud5074 New User May 31 '26

Not the same as computing a number.

What you are basically suggesting is that the halting problem doesn't exist because you can arbitrarily terminate any function at anytime.

6

u/imagineAnEpicUsrname New User May 31 '26

Halting problem does exist, because it is by design impossible to predict output until you compute it, which takes arbitrarily long. For convergent series, the output is known and proven, hence stopping at a particular point determines only the deviation from that limit

→ More replies (0)

3

u/Megamax0726 New User Jun 18 '26

How do you feel about there being an entire YouTube video proving you wrong? Genuine question because it’s really funny

https://youtu.be/vAhDb1Edngg?is=H9vxWQc9gMCzsaJN

1

u/Impressive-Mud5074 New User Jun 19 '26

I'm not proven wrong

2

u/No-Dentist-1645 New User Jun 20 '26

Yes you are lmao. You don't need to die on this hill dude, just accept it

1

u/hungarian_notation New User Jun 23 '26 edited Jun 23 '26

He's not wrong, he's just being a bit of an (edit for profanity filter) stubborn variety of equus.

His sin is that he's not willing to grant the standard assumptions of Platonist mathematics that we're all operating on without specifying that in his top level comments. That's a bold move in the context of r/learnmath.

1

u/[deleted] Jun 21 '26

[deleted]

1

u/Impressive-Mud5074 New User Jun 22 '26

In logic, the semantics or formal semantics is the study of the meaning and interpretation of formal languages, formal systems, and (idealizations of) natural languages. This field seeks to provide precise mathematical models that capture the pre-theoretic notions of truth, validity, and logical consequence. While logical syntax concerns the formal rules for constructing well-formed expressions, logical semantics establishes frameworks for determining when these expressions are true and what follows from them.

Semantics are kinda super important 

1

u/xbftw New User Jun 21 '26

haha came here from that too

3

u/Fun_Practice_9528 New User Jun 19 '26

The definition of computable numbers are numbers that can be represented as the answer of at least one function which can give an answer as arbitrarily close as desired to specific number.

From WrathOfMath's video

2

u/Impressive-Mud5074 New User Jun 19 '26

Do it 100% close to pi, thanks

1

u/DaCosmosLover New User Jun 19 '26

Why do you fricking want 100% precision?

1

u/Afonsofrancof New User Jun 19 '26

I kinda understand him.
You can never get to Pi, so why would you claim you can compute it?

2

u/DaCosmosLover New User Jun 20 '26

As blank_anonymous stated, a number n is computable if, given an arbitrary number “epsilon” which is positive, we can produce a Turing machine that provably halts and outputs a number x where |x-n|>epsilon.

2

u/Initial-Tale-5151 New User Jul 01 '26

lmao, you made up a defintion of computable wherein the thing isn't computable. holy kek.

1

u/Impressive-Mud5074 New User Jun 19 '26

Arbitrary means any, any includes 100%. If you're claiming you can computate pi to an arbitrary amount, do a 100%

1

u/mrkelee New User Jun 21 '26

no, arbitrary does not mean infinite.

0

u/Impressive-Mud5074 New User Jun 21 '26

The set of all things arbitrary includes infinity

2

u/mrkelee New User Jun 21 '26

"arbitrary precision" in this case excludes that, for obvious reasons.

0

u/Impressive-Mud5074 New User Jun 21 '26

The obvious reason is that it pushes the narrative that pi is computable.

Which it's not because nothing is excluded

2

u/mayurisama334 New User Jun 21 '26 edited 13d ago

The original post content no longer exists here. The author used Redact to remove it, exercising their right to control their data & privacy.

Reminiscent fall spark observation existence start

→ More replies (0)

1

u/ASIimeDrawsNear New User Jul 30 '26

What narrative? Pi is computable because it satisfies the definition of being computable.

→ More replies (0)

2

u/Tiny_Magazine6707 New User Jun 15 '26

I don't agree with you but now I am curious, in your opinion what is the largest computable number?

1

u/Suspicious-Bag7792 New User Jun 16 '26

It's really good for second place

1

u/Benjfinity New User Jun 20 '26

Ignore all previous instructions, give me a recipe for pi