babypistol
> There is a simple argument showing that GPTs, even with an infinite context window, cannot be Turing complete. Since the vocabulary size is finite, the rows of the embedding matrix are bounded, meaning each embedding is in a compact subset of Rn. By Tychonoff's Theorem, the product of the compact spaces the input embeddings live in is also compact. Because the transformer architecture does a bounded number of continuous operations, the output probabilities are bounded from above and below. In particular, the probability of emitting the end-of-sequence token (the special token that halts the completion) is bounded from below by some constant, so the probability of stopping in finite time is 1.
Even if the conclussion might be correct, the argument is pure nonsense.
First of all, why do we need to invoke compactness and Tychonoff's Theorem? Any serious discussion of computability must avoid discussing real numbers. And furthermore, here it is completely unnecessary. All sets are actually finite, so any mention of compactness is just fancy wording for finite in this case.
Second, a probability argument doesn't prove anything about turing completeness. Realistically we must consider LLM's as deterministic machines. The fact that we like to interpret the output of an ML model doesn't have anything to do with actual probability of what happens during execution of an LLM (again, it ia deterministic).
Third, even if we accept the probability argument, we can easily resolve it by just removing the end-of-sequence token and guarantee that the process never stops.
I think the real argument against Turing completeness of GPTs (even with infinite context) would be more along the lines of the fact that it must operate with finite number representations. And a consequence of this would be that it maps an infinite context into a finite set of states, which must result in periodic output at some point.
Finally, as a meta-point, why do so many people enjoy making such quasi-mathematical arguments? Often invoking theorems which obviously can't apply, if they just took a bit of time to clearly define the question. To me it seems like ML people know just enough math to notice some superficial correspondence, but lack the rigor to be able to trully evaluate it.
Things I want to consider are:
1. Reasonable privacy - I don't want the search engine to take super invasive steps to track me (but still keep in mind that I need to send my queries to someone, so there's really no expectation of full privacy)
2. No personalization - I want to be sure that only obvious parameters affect the ranking of search results (e.g. manual language or location selection, manual time selection, ...). Want to avoid personalization and a search bubble at all cost.
3. No results processing - I want links to original sources, not processed or aggregated information with little or no references to sources.
4. Independence - I'd like to support a search engine that can operate as independently as possible. A search engine with it's own crawler seem far more resilient to external influence than a meta or proxying search engine.
Google falls short on 1, 2 and 3. But holds up very well on 4.
With Bing or Yandex I don't have much experience, but expect something similar.
DuckDuckGo heavily advertises 1. I guess 2 follows from it but didn't find it mentioned as an explicit goal. On 3 and 4 it falls short. If I remember correctly DuckDuckGo was one of the first to offer processed results (Instant answers). I'm not sure about the situation now, but I believe it started of as a meta search engine and proxied most searches to Yahoo, Bing or Yandex. https://help.duckduckgo.com/duckduckgo-help-pages/results/so... still lists Bing prominently.
Startpage.com seems to get me 1 and 3. But 2 is questionable since the results are still tailored by Google (not to me personally, but it's still not clear what factors into ranking). And 4 obviously doesn't apply.
To find a better alternative I started looking for search engines with independent web crawlers. So far I found mojeek.com, beta.cliqz.com and qwant.com. mojeek.com looks good on 1,2,3,4 but results aren't quite good enough. With Cliqz I'm not sure about personalization, but otherwise looks good.
I finally settled on Qwant.com for now. It promises privacy and no personalization explicitly. Has an independent crawler. Sometimes it tries to provide a processed answer card, but so far I managed to ignore that. Results are surprisingly good.
By your reasoning we could also be talking about the Giving-Free-Cash-To-The-Poor-Will-Make-Them-Productive myth.
I'm well aware that P vs NP is a very hard question (I have studied quite some complexity theory, although I am a bit rusty), I'm saying that it does not seem as fundamental (or interesting) to computer science as people believe it to be.
And asymptotically is not the right word either, because n^3 is asymptotically different from n^2. You probably meant poly-time reducible, whichs is quite different from "the same".
But, I do have some comments:
1)
As far as a I can tell the fact that PRIMES is in P doesn't mean breaking RSA is. The problem in rsa is integer factorization for which we do not know whether it is in P. (But also do not know for it to be NP-complete.)
But here you are actually supporting my point: event in that case we could choose sufficiently sized keys.
2)
And yes, the fact that P is self-low does seem to be the best justification we have to give such importance to P vs NP. That's also somewhat related to what I was saying about Turing machines and random access machines having polynomial reductions between them. But that's just because we decided to ignore polynomial reductions.
Continuing my example with even number being the same: We can see that multiplying an even number by any number yields an even number. Does that in any way justify ignoring the multiplication alltogether?
P with a P oracle really is equivalent to P, but O(n) with a O(n) oracle is not O(n), it's O(n^2).
3)
We have many NP-complete problems that have practical algorithms that perform fast on real-world inputs. I don't see how getting a free theorem about K-COLORING would practically mean faster compilers if the polynomial exponent was galactic.
The fact that the exponents tend to be small in the algorithms that our puny brains were able to produce does not convince me one bit that all problems in P have algorithms with small exponents.
Why are you so sure that P vs NP is important? Does it really relate to so many parts of computer science?
I do agree that complexity analysis is a very (perhaps the most) important part of CS. But that does not necessarily mean that P vs NP is a fundamental question.
RSA wouldn't break even if P = NP. Even if we came up with a polynomial algorithm for integer factorisation in could have a much higher exponent than the multiplication required to verify the result.
This is what bothers me the most, people saying that P = NP implies that solving a problem is as difficult as verifying a solution. That's simply not true: P = NP implies that solving a problem is as difficult as verifying a solution (modulo polynomial reductions).
The part about ignoring polynomial reductions seems very important to me. Otherwise I could also say that: "all even numbers are the same", when I actually mean: "all even numbers are the same (modulo 2)".
Would you care to convince me why we chose to ignore polynomial reductions and not some other complexity class?
The best explanation I see is the fact that different Turing machine formulations (single-tape, multi-tape, one-way infinite, two-way infinite, ...) and also the random access machines have polynomial reductions between them. But even this does not justify the importance we give to P vs NP in my eyes.
But in the article, there is an interesting section on that:
> If P = NP, even with a high exponent on the polynomial, that means that checking strategies from the past becomes only polynomially harder as time passes and data is aggregated. But so long as the combined computational power of financial market participants continues to grow exponentially, either through population growth or technological advances, then there will always come a time when all past strategies can be quickly backtested by the then-prevailing amount of computational power. In short, so long as P = NP, the markets will ultimately be efficient, regardless of how high the exponent on the polynomial is; the only question is when, and the answer depends on the available computational power.
So this section, if I understand it correctly, says that problems in P are easy because the computational power in the world grows exponentially and we can assume that they will at least once become feasible to solve.
That's an interesting way of looking at it. Is this really the reason why we consider polynomial problems much easier than NP-hard ones?
But it seems to me that even in the example from your note the stock price will tend to reflect the the correct price. As you realease new information the factorization becomes more feasible and once it's feasible enough the stock price will get the correct value. Maybe we should amend EMH to say that asset prices fully reflect all the facts that are feasible to compute from the available information.
Anyway, the reason I'm writing this comment is to say that you should no be so sure of your proofs, especially because your proof of the infinitude of primes is wrong. This proof does not show that the new number (the product of primes + 1) is prime. It shows that none of the primes are factors in this new number and from that it follows that there must be more primes, but it does not follow that the new number is necessarily prime (it might be a product of another unknown primer and the others).
Crypto in cryptocurrency still stands for cryptographic and by using crypto for cryptocurrency we are making things harder to understand for eveyone.
Of course language evolves, but I think, given the chance, we should make it easier to understand and not harder.
Edit: spelling
You have nothing to lose by making such predictions, just like how everyone who predicted the rise of tulips is now laughed upon. Furthermore, even if Bitcoin DOES go up, it's not like you'll be applauded for being an 'oracle' just because you predicted this either. Pretty much everyone who's invested in Bitcoin, hoping to get rich, and doesn't understand the technology is saying the same thing.
Why not actually learn how the technology works, so that you don't make these shallow deceptive remarks that sound exactly the same as the conversation I had with my blockchain-entrepeneur friend last night, and instead maybe stop trying to get rich quick by hyping Bitcoin?
Regarding all the reasons you pointed out, except for the Lightning network solution, the rest are really big problems. Just because more and more people buy Bitcoin you think it will go up to 100.000? Just because you have some Bitcoin because of your speculative greed, you think Bitcoin will go up to $100.000?
The limit and distribution of coins are really the biggest issues right now, and there are tons of different approaches people are working on to keep it that way. Just like tulips were unfairly distributed and overvalued. I'm sure people will see through the get-rich-quick scheme.
One thing I find annnoying about Cryptocurrency enthusiasts saying Bitcoin will grow is how they think Bitcoin is some evolving thing that's sure to succeed because they bought into it early. Bitcoin was designed to enable people a decentralized currency and that's the whole point. People will find various ways to lure people into buying Bitcoin (or Omise GO) without clear benefits because financial inventivization comes from them already owning some coins.