Turing Tarpit | Hacker News Reader

Turing Tarpit

en.wikipedia.org

65 pointsjaytaylor30 comments

My favorite Turing tarpit is FRACTRAN, devised by John Conway. It's flabbergasting that it is actually Turing complete, but it is.

A FRACTRAN program is a list of fractions, rational numbers. You input an integer and then you find the first fraction that gives you an integer when multiplied by your input. That process is repeated with the new, multiplied number until there is no fraction that produces an integer when multiplied.

Conway wrote a program that generates primes, there's others that mathematical sequences, but my favorite is just the addition program:

3/2

Given an input 2^x * 3^y, it will stop at 3^(x+y), which adds x and y together.

For the lazy: https://en.m.wikipedia.org/wiki/FRACTRAN

For some reason this makes me imagine an alternate history sci-fi universe where Pythagoras (famous for his love of fractions) invents FRACTRAN. Then Archimedes builds a mechanical computer to execute those programs, and one of the successors of Alexander The Great puts the computer to use in warfare and conquers the world. Science is accelerated so that nuclear physics are invented by the time Jesus is born... Surely there's some kind of plot waiting there :)

"My words are backed with NUCLEAR WEAPONS!"

I think this article is missing a description of the phenomenon "accidentially turing-complete". Configurations langues or DSLs that over the time evolved and somehow got turing complete. I suspect these are the most common turing tarpits. And it's a horrible smell.

That's kind of an interesting one: consider two configuration languages. The first is not turing complete and can be considered a good language. The second is an identical copy of the first, but includes the ability to have recursive definitions which ends up making it turing complete.

Is the second language really worse than the first? They can both be used the same way, but the second one can allow for some shortcuts in configuration by abusing turing completeness.

I'd guess the arguments would be: the 2nd language is better, it can create an identical configuration in less lines. Alternatively: the 1st language is better as should allow for easier parsing and is simpler to verify for correctness.

> the 2nd language is better, it can create an identical configuration in less lines.

A simple macro or syntax sugar could save you the same lines. A good language will give you a good, terse syntax for representing common configurations, and enough flexibility for clearly denoting the uncommon ones. If your configuration is particularly obscure, it should need more lines to express.

It is not worth sacrificing verifiable correctness to induce this kind of gain when there are better ways of doing it.

Be careful, 'lest your macro language itself turn Turing-complete.

> It is not worth sacrificing verifiable correctness to induce this kind of gain when there are better ways of doing it.

It's also important to remember it's not always worth sacrificing power to gain verifiable correctness. Not every class of problems needs it.

"Freedom for security", something something. ;).

The 1st language isn't just simpler to verify for correctness, the 1st language is possible to verify, while the 2nd is not verifiable. Turing complete languages are a singularity beyond which we cannot reason about behavior for arbitrary programs. For many tasks- installation scripts, serialized data, etc- it is extremely undesirable from a security standpoint and for the purposes of writing tooling to permit arbitrary computation.

There was an interesting submission about your qustion earlier today, https://news.ycombinator.com/item?id=10567408 There the author is arguing that simpler is better, I guess the discussion there eventually spawned the submission of this one.

I can think of a couple examples off the top of my head --- TeX and template metaprogramming. Although I think Knuth protests too much when he says that he tried not to make TeX Turing complete. At any rate, in both cases, Turing-completeness should be considered a hazard. There should be a warning label on TeX, particularly:

WARNING: TeX is Turing complete. Proceed with caution!

I like it. Is there a term for the opposite situation? Where you're operating in a declarative environment, what you want to do should be possible, everything similar to the thing you want to do is possible, but your particular use case is excluded due to lack of foresight/manpower/understanding by the authors?

(Obviously not entirely specific to non-Turing-complete environments but they tend to be the worst offenders and the hardest to work around for obvious reasons.)

Not an opposite situation, but avoidance of this issue (mostly related to management of state) is outlined in the fantastic paper 'Out of the Tarpit' - which in my opinion every developer should read at least once.

http://shaffner.us/cs/papers/tarpit.pdf

Ironically, that 66 page document is a massively overcomplicated discussion of the simple idea that inessential mutable state causes problems.

Funny enough I have been doing a deep dive on production rules and logic programming lately, facing up to why the technology has not caught on more than it has.

One thing I find is that novices are creating rule bases that form infinite loops and that the CS community has been paralyzed by the fear of infinite loops and poor scaling for particular reasoning chains.

Working with mainstream languages, however, I don't find infinite loops (or Turing's Halting Problem) to be all that relevant and the big reason is that the mainstream languages that people like to complain about already have structures built in that make infinite loops less likely to happen.

It's worth noting that, even if a language is a Turing Tarpit, it doesn't mean there's no value in it. For example, I think of Brainfuck as a brilliant language to introduce people to writing interpreters.

I posted this link after seeing it in this [0] article condemning functional programming languages. While I don't necessarily agree that FPL's should be avoided, I was hoping some interesting discussion might emerge from it.

[0] https://news.ycombinator.com/item?id=10566899

That article was a fairly factless rant. To my mind, while there may be good reasons to avoid FPLs, that article doesn't present any. It reads like it was written by an angry non-technical co-founder, and its use of images was more appropriate to Buzzfeed than HN. There are certainly more businesses where an army of mediocre Java or PHP programmers are sufficient to keep a piece of software in a useful state than there are environments where you need FPLs, but blanket condemnation is not really worth the time it takes to read. Also, equating a $60k PHP dev and a $150k Haskell dev is likely to be a serious error. And of course, describing FPLs as Turing Tarpits is indefensible.

In other words, there's not much in that article to discuss.

Fair enough, thanks for your thoughtful analysis!

I shared that same link a couple days ago, mostly hoping to see if it sparked some interesting convo. No one bit. It's a silly article though given that it's pretty clear that functional programming is actually taking over, bit by bit. Not so much the functional languages themselves, but the techniques -- Python's comprehensions, Ruby's blocks, Javascript's Underscore library, and so on. I guess it's debatable whether real startups should go "full functional" but as traditionally imperative and traditionally functional languages continue to converge, it probably matters less and less.

I don't think FPLs by themselves are (Turing) tar pits. On the other hand, there are lambda-calculus tar pits - for example SKI combinators. This shows that even a language that has referential transparency and lazy evaluation can be a tar pit; so these qualities by themselves are not a way to avoid complexity.

I hope one day we will be able to mathematically formulate what is "unnecessary complexity".. but so far, no idea.

I'm pretty sure the person that wrote that is either a troll or mentally ill. All of their posts are poorly written anti-functional programming rants. They're also on reddit with the same sort of thing.

And Twitter. It's an insultingly obvious troll account, and... I think that's half the point.

They can be entertaining, though, if you don't get enough of annoying coding hassles at work! To that end there's a miniature genre of programming puzzle games on the PC. I'd recommend Human Resource Machine, SpaceChem, and TIS-100 for starters.

This reminds me of something my voice teacher used to say to me in criticism of my flamboyant style of jazz improvisation, and it's my basic philosophy on interface design (of all kinds): "Just because you can, doesn't mean you should."

I also apply it to improvisation. :)

Designing and implemeting one of this languages is fun and useful to learn how a Turing machine works. I'm not really into PL design, but I guess this could be a good task to get started.

At university I had great fun creating a functional programming language that macro expanded to lambda calculus that was then "compiled" to various sets of combinators - I still find the fact that you can express recursive progams using Y purely in terms of two trivial function (S and K) to be one of the most surprising things in CS.

I suspect any Lisp is a Turing tarpit.

> A Turing tarpit (or Turing tar-pit) is any programming language or computer interface that allows for flexibility in function but is difficult to learn and use because it offers little or no support for common tasks.

Which common task could you not perform with Lisp?And if you are stressing on the `Little or no support`,then thats true any of the lesser popular languages isn't it?

Are you sure you don't mean any Lisp is a Turing Carpet, with all those curling parenthesis nestled warmly together like deep twisting loops of shaggy pile?

Reply on news.ycombinator.com