Remix clone Hacker News

Nobody is talking about a finite state machine in complexity. Its time complexity is n, and its space complexity is 0. The Halting Problem specifically pertains to Turing Machines.

▲

graycat 5 days ago | parent [-]

What I wrote is correct but does not address the traditional Turing Machine halting problem or solve it.

The traditional halting problem is theoretical, i.e., not close to anything practical, and so is what I wrote.

And I did not claim that what I wrote is a contribution to "complexity theory".

The Turing Machine Halting Problem has long been standard computer science; from that it's common to conclude we can't tell if a program will stop. But that conclusion needs some theoretical assumptions, and my version is simpler and shows that we have to be careful drawing conclusions from the standard treatment.

▲

tgv 5 days ago | parent [-]

> What I wrote is correct

What your wrote is pretty much trivial, and not related to the topic of the article.

It's also not practical, since the space needed to represent even a small program as an FSM is very large. Just try to write an FSM that reads binary coded 16 bit numbers, and has to find the maximum value. Now imagine sorting just 100 of them.

	▲	graycat 5 days ago \| parent [-]
		> What your wrote is ... not related to the topic of the article. The article was: The Halting Problem is a terrible example of NP-Harder and I wrote: > So, in this case can tell if the "program will stop" and, thus, solve "the halting problem". > "Trivial"? I never claimed the post was a significant contribution to computer science or complexity theory, and at most only a tiny fraction of posts at HN are such. Also, my post does not address the complexity theory question of P = NP. If what I wrote was "new, correct, and significant", then I should have sent it to a good computer science journal. I've published enough papers in good math and computer science journals to notice that the checks take a long time to arrive. I'm not in academics and never wanted to be. HN is not a journal of new, correct, and significant work in computer science. From responses in this thread, the post has proven to be at least curious and interesting to some of the HN audience.