Comment by lsy

Comment by lsy 4 days ago

Note that for the purposes of this paper a “problem” just means a formally decidable problem or a formal language, and the proof is that by creatively arranging transformers you can make individual transformer runs behave like individual Boolean circuits. However, this is a long way from any practical application of transformers: for one thing, most problems we care about are not stated as formal languages, and we already have an exceptionally more efficient way to implement Boolean circuits.

shawntan 4 days ago

If a "problem we care about" is not stated as a formal language, does it mean it does not exist in the hierarchy of formal languages? Or is it just as yet unclassified?

Reply View 23 replies

tsimionescu 3 days ago

It means that there are two problems: one, to formalize the problem as stated while capturing all relevant details, and two, solving the resulting formal problem. Until you solve problem one, you can't use formal methods to say anything about the problem (it's not even clear a priori that a problem is even solvable).
Unfortunately, the task of a formalizing an informal problem is itself an informal problem that we don't know how to formalize, so we can't say much about it. So overall, we can't say much about how hard the general problem "given a problem statement from a human, solve that problem" is, whether any particular system (including a human!) can solve it and how long that might take with what resources.

Reply View | 20 replies
- viraptor 3 days ago
  
  > task of a formalizing an informal problem is itself an informal problem
  I couldn't find details about this - do you know of a paper or some resource which digs into that idea?
  
  Reply View | 19 replies
  
  tsimionescu 3 days ago
  
  No, but it's pretty obvious, isn't it? If you have an informal problem statement, say "I want this button to be bigger", formalizing it can't be a formal process.
  
  Reply View | 17 replies
  
  esjeon 3 days ago
  
  Ah, you are informally inquiring about a formal description concerning the informal nature of formalization of informal questions.
  Joke aside, this is about the nature of the formalization process itself. If the process of formalizing informal problems were fully formalized, it would be possible to algorithmically compute the solution and even optimize it mathematically. However, since this is obviously impossible (e.g. vague human language), it suggests that the formalization process can't be fully formalized.
  
  Reply View | 0 replies
wslh 3 days ago

My 2 cents: Since LLMs (Large Language Models) operate as at least a subset of Turing machines (which recognize recursively enumerable languages), the chain of thought (CoT) approach could be equivalent to or even more expressive than that subset. In fact, CoT could perfectly be a Turing machine.
If we leave CoT aside for a moment, it's worth exploring the work discussed in the paper "Neural Networks and the Chomsky Hierarchy"[1], which analyzes how neural networks (including LLMs) map onto different levels of the Chomsky hierarchy, with a particular focus on their ability to recognize formal languages across varying complexity.
[1] https://ar5iv.labs.arxiv.org/html/2207.02098v1

Reply View | 1 reply
- flir 3 days ago
  
  > In fact, CoT could perfectly be a Turing machine.
  Are we going to need an infinite number of LLMs, arranged on a tape?
  
  Reply View | 0 replies

julienreszka 3 days ago

> most problems we care about are not stated as formal languages

then a way would be to translate them to formal language

Reply View 0 replies