Talk:Turing tarpit

The concept of symbol

I have a feeling that what Minsky and Bobrow meant by "symbols" wasn't the same thing as saying that, say, binary combinatory logic only has "2 symbols". In fact, BCL is only a binary representation of a system that has 3 symbols. It's like saying that UTF-8 is an advanced encoding because it only has 2 types of bits – the 0 and the 1. You can format any language as binary and hence unary if you want to. Rather, I would argue that reserved words in C are symbols as well. Kumiponi (talk) 08:10, 7 August 2013 (BST)

Unary's operation count

Shouldn't Unary be listed as having 8 operations, 1 symbol? --CreeperBomb (talk) 22:50, 3 May 2023 (UTC)

Qualifying further additions

Following up from a question on my user talk page: it seems like there are rules now, what's up with that? In order to stay sane, I'm asking for folks to consider the following criteria before adding to this page. The main issue is that our notion of "machine" has vastly generalized in the past seven decades or so, and we now study many non-Turing-machine tarpits. So, here's what I'm proposing. Some of this was already implicit and we're just stating it openly. Feedback is welcome; reply to this paragraph before changing the subsections, please. Corbin (talk) 17:20, 1 December 2025 (UTC)

Languages

There is nothing new to add here; any changes need to be interesting. That said, this is the least-organized part of the page, and I'm open to better ways to manage it.

• Must be a language: given an alphabet, must be a subset of all strings of that alphabet
• Must be Turing-complete: must be an undecidable subset which can represent Turing machines or something other Turing-complete machine
• Must be computable: must be implementable on some Turing-complete machine

Metrics for languages:

• Cardinality of alphabet
• If grammar: number of productions? length of longest production?

Universal TMs

• Must be a program for a TM
• Must have a fixed number of states and symbols

Metrics:

• Number of states
• Number of symbols

Combinatory logic

Contributions must improve on the state of the art and summarize combinatory logic.

• Must be a basis of combinators
• Must really be combinators, not closed lambda terms: must take applicative trees as arguments and produce an applicative tree

Metrics:

• Number of combinators
• Minimum rank

Closed lambda terms

Contributions must improve on the state of the art and summarize closed lambda term. Contributions should improve on the open question by having Fokker size between three and seven, or by introducing and justifying a new metric; in the latter case, I can do the work to formalize everything sufficiently and add the numbers to the section.

One-instruction machines

There is nothing new to add here; any changes need to be interesting.

• Must manipulate encodable arguments (ints, pointers, etc.)
• Must be uniform over decoding, rather than smuggling opcodes in as arguments; that's literally the construction which turns any machine into an OISC
• Must not cheat by packing multiple arguments into one argument, although run-length encoding for sequences of instructions is acceptable

Metrics:

• Number of arguments

Zero-instruction machines

There is nothing new to add here; any changes need to be interesting. I would suggest that it's not worth trying to add a new ZISC here.

BinaryLanguage should not be a tarpit

It has over 10 commands ↑ (↑↑↑) 21:27, 1 December 2025 (UTC)

Tarpitness means that the language is able to be a Turing machine, it's just hard to use it

User:Gaham (Discord:glebovsky_)

It actually means that it's a turing complete language with a minimal amount of instructions. mariomakercalculator↑↑↑↑↑↑↑↑↑↑↑↑↑↑ 15:46, 2 December 2025 (BRZ)

But languages don't have instructions, just an alphabet of letters. So either it's more nuanced than that, or somebody has defined something wrong. Corbin (talk) 18:57, 2 December 2025 (UTC)

What is the limit to The Turing Tarpit?

what's the maximum n instructions, m symbols? where's the line?? --JIT_{JITJITJITJITJIT} 10:30, 5 January 2026 (UTC)

There isnt one --Yayimhere2(school) (talk) 11:12, 5 January 2026 (UTC)

Let's say five instructions, five symbols. Corbin (talk) 16:43, 5 January 2026 (UTC)

A better limit would be the maximum instructions and symbols of bf, the entry with the most instructions in the list. mariomakercalculator↑↑↑↑↑↑↑↑↑↑↑↑↑↑ 17:28, 5 January 2026 (BRZ)

Sure, but at that point I'd like you to figure out whether Brainfuck is a machine or a language! I think that Brainfuck is often implemented on top of an eight-instruction machine. However, algebraically, we don't actually know yet what the minimum size of the alphabet (its monoidal rank) is; see Algebraic Brainfuck, monoid#rank, BF instruction minimalization, and bluelinks therein. Corbin (talk) 23:01, 5 January 2026 (UTC)