Also do you know of anything non-random? It's still highly desirable for me do narrow this down to a single input

Both of these are strong answers, particularly polynomial identity testing. I wonder if something like arxiv.org/abs/1909.03391 exists for multilinear functions. If so you could dispense with the assumption that we've inspected the code to obviously produce a multi-linear function (that said in my original case this is a strong and often valid assumption that I've been working with, I just didn't know the right term was "multilinear").

I'll remove extraneous parts and clarify.

The language of turing machines that accept undecidable languages is empty and therefore decidable by the Turing machine that never accepts.

Ah I see. Hmm, maybe that could work? It's a good question that needs a proper formalization I think. Now that I understand what you mean a bit better I think it depends on the formalization. If we use basic blocks as "states" then I suspect the answer is still "no" because you can encode undecidable problems without control flow...if we use Turing machine states then I'm not sure this enables any optimization. Also for some definitions of this I can imagine we're not able to remove branches that don't effect the final outcome which seems important to an "optimal" optimizer.

It's still not computable if you cook up some "uneeded infinite loop oblivious" equivalence relation. Or rather such an equivalence is not a well formed idea. Consider a program that loops until it finds a solution to an instance of hilberts 10th problem and then outputs the solution. If a solution exists then it should print out the solution but otherwise it prints out nothing. The optimal program would for a solvable instance just print the solution and print nothing when there isn't a solution. So such a compiler could solve the 10th problem but optimizing and then running the program.

I really fixated on the constants part of this and missed the part where it mentioned that variables also can't go above 17. That's actually the critical part here. Even if constants could be as large as possible, as long as variables somehow can only ever by 17 at most the theorem holds.

Recursive == Decidable. They mean the same thing. So if you ask if "Are languages (of any category) which are not Recursive, also Undecidable?" the answer is "yes, definitionally"

I'll add another thing to this. Why do you want to avoid learning something? I spent a lot of time having a bias against certain types of mathematics that I didn't find pleasing but frankly that didn't help anyone. I also had a bias against a lot of OOP things and associated tools but that didn't help me either. You're far better off trying to leave your bias behind. Who cares if you learn something useless along the way? I've learned tons of useless things. The useless things are some of my favorites!

You can learn any part that isn't OOP. OOP is a tiny tiny tiny subfield. I'd call it a vouge idea in industry in the 90s and early 2000s. In industry nowadays we're seeing a movement away from that. When learning to program I understand why people think its so important but from a theory standpoint it isn't important at all and even from an industry perspective the idea is loosing ground.

practical answer that isn't helpful to the conceptual question here: many modern relational databases allow for array data types that would probably work for you. Better Answer: Good question! I don't know the best way to do this! You don't need a tree to do this efficiently I think. You can just use a linked list with the primary key of the node table being used like an address. Removal requires a transaction with one update and one deletion. Insertion requires a transaction with one read, one insert, and one update. Each node would have a primary key, a list id, a next key, and content

Assuming S isn't decidable dosn't allow you to use it as an oracle. That is a separate interesting question "what sets S is T_m decidable for if we have an oracle for S" but not the one being asked.

What have your tried?