A (2,3) Turing machine can be trivially implemented with a loop around an LLM that treats the context as an IO channel, and a Prolog interpreter runs on a Turing complete computer, and so per Truing equivalence you can run a Prolog interpreter on an LLM.

Of course this would be pointless, but it demonstrates that a system where an LLM provides the logic can backtrack, as there's nothing computationally special about backtracking.

That current UIs to LLMs are set up for conversation-style use that makes this harder isn't an inherent limitation of what we can do with LLMs.

▲ measurablefunc 6 days ago | parent [-]

Loop around an LLM is not an LLM.

▲ vidarh 6 days ago | parent [-]

Then no current systems you are using are LLMs

▲ measurablefunc 6 days ago | parent [-]

Choice-free feedforward graphs are LLMs. The inputs/outputs are extensionally equivalent to context and transition probabilities of a Markov chain. What exactly is your argument b/c what it looks like to me is you're simply making a Turing tarpit argument which does not address any of my points.

▲ vidarh 6 days ago | parent [-]

My argument is that artificially limiting what you argue about to a subset of the systems people are actually using and arguing about the limitations of that makes your argument irrelevant to what people are actually using.

▲ measurablefunc 4 days ago | parent [-]

So where is the error exactly? Loop around is simply a repetition of the argument for the equivalence between an LLM & a Markov chain. It doesn't matter how many times you sample the trajectories from either one, they're still extensionally equivalent.

▲ vidarh 2 days ago | parent [-]

Since an LLM with a loop is trivially and demonstrably Turing complete if you allow it to use the context as an IO channel (and thereby memory), by extension arguing there's some limitation that prevents an LLM from doing what Prolog can is logically invalid.

In other words, this claim is categorically false:

> Logical reasoning as it is implemented in Prolog interpreters is not something that can be done w/ LLMs regardless of the size of their weights, biases, & activation functions between the nodes in the graph.

What is limiting "just" an LLM is not the ability of the model to encode reasoning, but the lack of a minimal and trivial runtime scaffolding to let it use it's capabilities.

▲ measurablefunc 2 days ago | parent [-]

> Since an LLM with a loop is trivially and demonstrably Turing complete

Where is the demonstration?

▲ vidarh 2 days ago | parent [-]

In every LLM app you have available that can set temperature.

You can try a template like this:

    Turing machine transition table:
    q₀, 0 → q₀, 0, R
    q₀, 1 → q₁, 1, R  
    q₀, B → q₀, B, L
    q₁, 0 → q₁, 0, R
    q₁, 1 → q₀, 1, R
    q₁, B → q₁, B, L

    Current state: [STATE]
    Current symbol: [SYMBOL]
    
    What is the next transition?
    Format: NEW_STATE|WRITE_SYMBOL|DIRECTION

You might have to tweak it depending on the given model you seek, but given you set temperature to 0, once you've tweaked it so it works on that model for all 6 combinations of state and symbol, it will continue working.

Repeat it, and provide a loop with the IO as indicated by the output.

If you struggle with the notion that an LLM can handle a lookup table from 6 combinations of states and symbols to 6 tuples, you're looking for excuses to disagree and/or don't understand how simple a UTM is.

The above is a sufficient definition for someone who understands a UTM to figure out how to execute the machine step by step.

	▲	measurablefunc a day ago \| parent [-]
		Let me know when you manage to implement the Fibonacci sequence w/ this. It should be doable since you seem to think you already have a Turing machine implemented on an LLM w/ a loop around it.