This bugs me a lot. If the spec is known how it is possible for some random reader to not being able to display it. Is pdf now somewhat html in late 90's where it was browser specified rather than specification?
987 karma · joined November 1, 2013
He then lists three most common examples of NP problems that are not even as close to the real problems as he thinks they are.
This is why the P versus NP problem is so interesting to people. If anyone were to solve it, it would potentially make very difficult problems very easy. and here is where he missed the point completely. This is simply not true - if for example there is polynomial time algorithm solving NP problem then P vs. NP is solved but if this algorithm is lower bounded by, I don't know, n^(10^80) it's not so easy for computers either. It is 'useless' from real software point of view.
The most profound effect of proving that P=NP is that the ability to check any answer's correctness 'fast' (in polynomial time) is sufficient to being able to solve that problem in polynomial time. That's it. Pure theory of computation. No real life super computing boost.
From wikipedia we read:
Turing completeness
A computational system that can compute every Turing-computable function is called Turing complete (or Turing powerful). Alternatively, such a system is one that can simulate a universal Turing machine.
From the first part I think compute means that from some input A there is output B. It is later explained in 'computable function' article:
Each computable function f takes a fixed, finite number of natural numbers as arguments. Note that the functions are partial in general, i.e. they may not be defined for every possible choice of input. If a computable function is defined for a certain input, then it returns a single natural number as output (this output can be interpreted as a list of numbers using a pairing function).
So if computable function is returning something that means it halts. We are able to compute every halting algorithm in preprocessor hence it is turing complete.
Second part of this definitions says that one has to simulate turing machine (and uses the word 'alternatively' so basically it has to be the same but I can go anyway). I think that 'simulate' in this context mean 'producing same output' rather than 'doing step by step the same'. Internal tape states at certain point in time should not matter because while running they might change (or if they matter we could just return list of pair {state,time} at the end).
There is no doubt that non-halting turing machines exists but I'm not sure if that apply to this particular problem anyhow since they are not computing anything.
And you're saying this based on what? Thanks for googling this for me, although the key-word was "comprehensive" not any definition.
But consider this: How one could say that this machine is actually writing "TM" every two cells? If you investigate tape states while machine is still running it might change (on meta-level you my expect that this is actually true but you might for example make some bug that you're not aware of). The only way to be able to see that "TM" has been written is after the machine halts.
[1] http://www.cis.upenn.edu/~matuszek/cit596-2012/NewPages/turi...
If yes, then not being able to re-enter old states disqualifies C preprocessor as a turing complete machine by considering simple machine that goes left and right till the end of time. However, is it really an algorithm? If there is no output one could simply replace that with just empty machine that halts for sure, therefore it can be simulated in C preprocessor.
On the other hand, if this is not requirement then we know that every algorithm we have to simulate to prove turing completeness halts eventually, there is no ability to re-enter old states but if algorithm halts we could just add enough more states (finitely many) that allows it to finish.
>The form you're likely most familiar with is Hexagonal Ice [...]. If you keep lowering the temperature of Hexagonal ice, it eventually becomes Cubic Ice; tweak the temperature and pressure further and you can create Ice II, Ice III all the way up to Ice XV.
I've counted 16.