babypistol

What is up with this argument that LLMs cannot be Turing complete?

> 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.

I have used DuckDuckGo a couple of years back, but, after some more consideration switched back to Google. Apart from privacy I never really liked the direction DuckDuckGo was going in (more below). Just recently I decided to search for an alternative search engine once again.

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.

Calling it a myth implies that there is adequate evidence to refute it.

By your reasoning we could also be talking about the Giving-Free-Cash-To-The-Poor-Will-Make-Them-Productive myth.

I don't understand why you are responding to me in such a condescending tone, but thanks anyway for the discussion.

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.

Well that's the problem, man.

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".

Thanks for the explanation.

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.

Well I'm trying to understand why this question is big.

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.

Yeah, in this case we are back to square one and P vs NP again seems irrelevant to me.

I have always been puzzled by why we as computer scientists give such importance to P vs NP. I always thought that even if P = NP the solutions might still be much harder (but only polynomially) to find than to verify. I always get angry when people say that P = NP would mean that problems would be equally as easy to solve as to verify. So, because of that, P v NP always seemed irrelevant to me.

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?

In my opinion P = NP does not mean that. There still might be a big polynomial difference between verifying a solution and finding one.

I haven't heard of EMH before today and can't really comment on that.

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).

Maybe it's just me, but I really don't like this view in this case.

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

Oh, I meant paper as a material. (And you probably got that.)

I think the problem is that blockcain fans mostly don't care about real crypto :) and use "crypto" as a synonym for digital currency. To me, saying "crypto" means blockchain seems like saying "paper" means book. Sure it is needed, but it is not really the most relevant thing to its function. We surely wouldn't call a pdf "paper" but I think some might call Ripple or even a simple sql database "crypto", and cryptography probably still is used in there to some degree but I think it is very far from the core.

I don't understand why people still do this type of "X will grow" predictions.

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.