Lightnews — Scholar-powered news

Helen @homotoptheory.bsky.social · 12m

bound, where (n, f(n)) is some subset of a computable subset of N x N consisting ONLY of pairs (n, m) for m>f(n)

Helen @homotoptheory.bsky.social · 12m

I was trying to think of a case where that infinite set was itself decidable that also satisfied that the product language was still decidable. This may be my lack of experience with the field but specifically, it is hard for me to think of a sequence f(n) which grows faster than any computable

1

Helen @homotoptheory.bsky.social · 1h

easier to read: mathoverflow.net/questions/50...

Understanding link between decidability and complexity

I've seen several instances where an undecidability/uncomputability result can be used to produce a lower bound complexity result, and I am interested in when the process can go the other way. In

mathoverflow.net

1

Helen @homotoptheory.bsky.social · 1h

oh wait the plot thickens, that $L$ isn't computable

1

Helen @homotoptheory.bsky.social · 1h

made an overflow account, typed the whole thing up, and then realized the answer is obviously NO. like, what if $L$ is just the set of pairs (n, BB(n)) for all numbers n. Then the sequence exists but P is trivial.

1 1

Helen @homotoptheory.bsky.social · 2h

i should probably post this to overflow if i want an answer not bluesky huh

1 4

Helen @homotoptheory.bsky.social · 2h

m up to the bound and this would provide a decision algorithm.

question: is the converse true? if i am able to prove the existence of such a sequence of instances, does this mean the problem is undecidable?

2 1

Helen @homotoptheory.bsky.social · 2h

in L?

Observation: suppose P is undecidable. Then there is a sequence of numbers n_i such that there is always an m_i with (n_i, m_i) in L, but m_i grows faster than any computable bound relative to n_i. Indeed, if it were not so, given any instance of the problem you could simply check all the

1 1

Helen @homotoptheory.bsky.social · 2h

Decidability question: Suppose you have a computable subset L of N x N, that is, elements of L are pairs of natural numbers, and given a pair there is an algorithm to determine whether that pair belongs to L. Then we can make a decision problem P which is, on input m is there an n such that (m,n) is