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 itUser: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)