If there's a proof that creating tallies or any sparse language in poly-time is impossible, then what's the significance of this decision problem?

[Secret_Very_Secret]

Is there a legit proof that creating tallies or any other sparse language in poly-time is impossible?

Or is this just a conjecture widely believed?

 

Please read the picture below before going to the links.

I have a paste-bin for an algorithm that solves my decision problem. https://pastebin.com/kuj2sZys

I have a repl link as well. https://repl.it/repls/WiryGrandioseSearch

 

 

 

 

[fiveworlds]

If you want to show that, you'd have to start by disproving that a universal Turing machine with no internal states need only be slower by a logarithmic time factor compared to the machine it simulates. Since logarithmic time < polynomial time it holds that since a then b. Their is a draft of the book where that was shown here  http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=EE1010E9E59F8CAA143C55745A49BD9A?doi=10.1.1.297.6224&rep=rep1&type=pdf

Edited October 5, 2019 by fiveworlds