Answers.Body: <p>You're right Turing machines are enough for current LLMs training and inference due to its recursively enumerable (RE) power regarding the generation of any valid strings of any computational language. While Context-sensitive language (CSL) is more expressive than CFL or RL and computational linguistics shows nearly all natural languages may in general be characterized by CSL, it still has limitations when it comes to capturing the <em>unbounded</em> dependencies and intricate patterns present in the training and inference processes of LLMs as indicated by <a href="https://en.wikipedia.org/wiki/Context-sensitive_language" rel="nofollow noreferrer">CSL reference</a>:</p>
  <blockquote>
  <p>Computationally, a context-sensitive language is equivalent to a linear bounded nondeterministic Turing machine, also called a linear bounded automaton. That is a non-deterministic Turing machine with a tape of only
  <span class="math-container">${kn}$</span> cells, where <span class="math-container">${n}$</span> is the size of the input and <span class="math-container">${k}$</span> is a constant associated with the machine.</p>
  </blockquote>
  <p>Therefore CSL is equivalent to a Turing machine with a finite tape of cells relative to its input and is apparently not enough for unbounded recursively optimizing and training LLMs which are nothing but specific hypotheses with their respective inductive bias only expressible in the RE language of mathematics for human or Turing-complete programming languages for physical machines.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-03-08T23:41:05.423Z
Answers.LastActivityDate: 2024-03-09T05:54:02.440Z
Answers.LastEditDate: 2024-03-09T05:54:02.440Z
Answers.UserDisplayName: cinch
Body: <p>We obviously know that Turing machines are enough for current LLMs training and inference. Are there languages behind the hierarchy that are enough for these processes (e.g. context-sensitive languages)?</p>
  <p>I assume there could be different language classes for training and inference.</p>
  
Tags: <machine-learning><computational-complexity><theory-of-computation>
Title: What kind of language in theory of computation language includes current LLMs?
UserDisplayName: sw.
ThreadText: # What kind of language in theory of computation language includes current LLMs?
  
  (Asked by: username_0 on 2024-03-08)
  
  We obviously know that Turing machines are enough for current LLMs training and inference. Are there languages behind the hierarchy that are enough for these processes (e.g. context-sensitive languages)?
  
  I assume there could be different language classes for training and inference.
  
  **Tags:** machine-learning, computational-complexity, theory-of-computation
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2024-03-08. Score: 1
  
  You're right Turing machines are enough for current LLMs training and inference due to its recursively enumerable (RE) power regarding the generation of any valid strings of any computational language. While Context-sensitive language (CSL) is more expressive than CFL or RL and computational linguistics shows nearly all natural languages may in general be characterized by CSL, it still has limitations when it comes to capturing the *unbounded* dependencies and intricate patterns present in the training and inference processes of LLMs as indicated by [CSL reference](https://en.wikipedia.org/wiki/Context-sensitive_language):
  
  > Computationally, a context-sensitive language is equivalent to a linear bounded nondeterministic Turing machine, also called a linear bounded automaton. That is a non-deterministic Turing machine with a tape of only
  > ${kn}$ cells, where ${n}$ is the size of the input and ${k}$ is a constant associated with the machine.
  
  Therefore CSL is equivalent to a Turing machine with a finite tape of cells relative to its input and is apparently not enough for unbounded recursively optimizing and training LLMs which are nothing but specific hypotheses with their respective inductive bias only expressible in the RE language of mathematics for human or Turing-complete programming languages for physical machines.
  
  
  ---
  
  