Is my cat Turing-complete?

https://belaycpp.com/2021/11/24/is-my-cat-turing-complete/

by zdyn5 • 5 years ago

286 88 5 years ago

I was almost out the door to pet shops and animal shelters so I could build a 16 cat-core setup over Thanksgiving. Then I figured I should at least read the full article before going through the trouble. It's a good thing too. Now I know that I should probably go for 64 cat-cores and treat it more like a quantum computer with the potential for rapid decoherence.

kreeben• 5 years ago

You could also buy just two then wait a while and through some inexplicable magic, you'll gave 64 cores of cat.

codetrotter• 5 years ago

I’ve heard that in order for this to work it is important to ensure that one of the cats is the Model M version and the other must be a Model F version.

Equally important, you must respond “No” when asked whether you want the “Neutering” feature enabled. This applies to both cats.

howdydoo• 5 years ago

Are these the big/little cores I've been hearing so much about?

zwirbl• 5 years ago

But be aware the resulting catsplosion will grind the simulation to a halt at some point

ineedasername6• 5 years ago

Ah yes, the famous "Meow's Law" of kitty density doubling.

zdyn5• 5 years ago

Going for the 5dm or 3dm node size?

crate_barre• 5 years ago

Apple makes their own cats now days.

d--b• 5 years ago

So, the 'cat-bit' is worth 1 if the cat is alive and 0 if the cat is dead? Now I understand why quantum computing requires so much funding...

ineedasername6• 5 years ago

Eh, cats are cheap. Most of the money is spent on drugs and liquor. Quantum computing is well known for its party atmosphere.

motohagiography• 5 years ago

Like Searle's Chinese Room, but with a cat in it, where observing it or asking it to do anything at all necessarily yields nothing, because it's a cat. Searledingers Catbox?

But more generally I'd ask the question of, if you can train a conscious animal to execute 8 brainfuck instructions (+, -, <, > , etc..), could they also develop a writing system and express higher order languge concepts? Asking why animals don't write assumes they can't, as maybe we just need some kind of intermediate symbolic phoneme concept, as though - like BF for computation, there are some basic unit instuctions that you can combine and parse into anything, and if a border collie can distinguish words for hundreds of different things, I'd wonder if what we're missing is a set of metaphors that represent this underlying core instruction set.

Things like musical notation and knitting stitch patterns are also thought to be Turing complete, so it implies the representation doesn't matter for computation, and computation is sufficient for representing most things, so the idea of finding some underlying instruction set for producing languages across species seems both fantastic yet loosely plausible.

simonh• 5 years ago

I'm sure you could train dogs, monkeys, or parrots to reasonably reliably perform logical operations. From that you could build a simple processor, but the error rate might be too high for it to scale much. It's not so much getting them to do the tasks, it's getting them all to reliably do them at the same time in synchronisation.

Of course as with the guy in the Chinese Room that doesn't speak Chinese, none of the individual animals would have any idea what the overall system was doing.

crooked-v2• 5 years ago

There are several Youtube channels where people gradually train cats and dogs to use boards full of buttons (20+ buttons in some cases) to communicate their wants. It definitely seems to work in general but doesn't make the animals any less themselves... one of the funnier examples being a video of a cat repeatedly pressing the "outside" button, staring at a yard full of snow, and then stalking back and pressing the "mad" button several times. Simple compound phrases (for example, "play friend" or "love grandma") are fairly common, but any kind of actual syntax is basically nonexistent.

stinos2• 5 years ago

64 cat-cores ... rapid decoherence

I'm glad you figured that 64 cat-cores is basically pure chaos. Well, for you, for the cores it's just their way of life: do random stuff for no apparent reason. Which is like the exact opposite of a computer.

ineedasername6• 5 years ago

Yes, if I can't get the system up & running for computational tasks, I figure I can always pivot the business model and sell its output as a world-class entropy source. My only problem is the lack of a moat around the model since anyone with a steady supply of cats, automated laser pointers, and a few hundred $/month in kitty kibble can reproduce my setup and make the whole thing a race to the bottom on price. I think at that point I could turn my accumulated knowledge into an excellent cat-entropy system servicing business, fine-tuning and optimizing other people's setups, advising on breed mixtures, laser speed, etc.

0xFFFE• 5 years ago

Do these cat-cores need cryogenic cooling?

dylan6042• 5 years ago

So the crazy cat ladies are really hardcore compute nerds that are just letting their cores rest?

ineedasername6• 5 years ago

They're trying to use the unique nature of cats to exceed the theoretical maximum of 1:1 bits of entropy. This would create an entropic contagion event and that spread a heat death out into the universe in all directions.

Cat ladies are evil nihilists.

anotherevan• 5 years ago

There's the makings of a science fiction novel in there, somewhere.

Intermernet• 5 years ago

Cats are a superset of Turing completeness. Cats are "undefined behaviour" https://bugs.launchpad.net/ubuntu/+source/unity/+bug/1463112

sdoering• 5 years ago

Thank you so very much. This just landed in my bookmark list of great bug reports that made my day.

I really like the way the community dealt with this.

(Disclaimer: My SO and me are also a foster home for cats. The cat behavior described is relatively normal esp. for one cat model currently "in use" here.)

lstamour• 5 years ago

I think my favourite part about the bug report is that it was closed as a duplicate!

This bug report is a duplicate of: Bug #1538615: Cat causes login screen to hang.

noisy_boy• 5 years ago

Chaos Cat - the final QA tester. Ensure that your service can survive it.

rob742• 5 years ago

Chaos Cat, a.k.a. the fluffy fuzzer...

rob742• 5 years ago

To replicate: In unity hit ctrl-alt-l, place keyboard on chair. Sit on keyboard.

I would recommend using a cat if available - otherwise, depending on the chair and on the weight of the tester, this might lead to permanent damage to the keyboard. I would definitely refrain from doing this if said keyboard is attached to a laptop.

secondaryacct• 5 years ago

Ahah super, bien joué la frontpage sur HN !

praptak3• 5 years ago

The ops don't seem to compose though.

Cats are smart critters, so I think it would be possible to train one to do a set of operations that's actually Turing complete. Cat behaviourists and comp sci folks could work together on this.

hef19898• 5 years ago

There is a guy in Russia who trained cats to do all kinds of circus tricks. Going from personal experience, a cat would be better suited to get a human to the calcalution for the cat then the other way round. If said cat is bored enough to bother trying so.

__alexs• 5 years ago

What the author calls cat computing I like to call crab computing. I think crabs are a better analogy because crabs have successfully been used to perform logic operations in a lab and cats have not.

telesilla• 5 years ago

Warning, don't click if you need to be productive. https://www.reddit.com/r/crabcats

colejohnson66• 5 years ago

And if you don't like Reddit's new interface: https://old.reddit.com/r/crabcats/

peanut_worm• 5 years ago

I tried to repeat this experiment and my cat had a Segmentation Fault

stinos2• 5 years ago

You mean an undefined period of Sleep()?

deusum• 5 years ago

You can expect a core dump.

dylan6042• 5 years ago

Only if a sandbox is available for that routine

marcodiego5• 5 years ago

The other day there was a wasp going in and out of my room on the second floor by the window. I closed the window because it was annoying me.

The wasp found an entry through another window, in another room open in the second floor. It was from the room next door. So, I just closed this other window.

Again, it found an entry from another window. But this time, it started to impress me: it was from a room across the corridor! The wasp flew to the back of the house, found an open window, entered it and mapped to path through the corridor to my room.

I then closed all the windows in the second floor of the house and bet it was over. I was wrong: the wasp came in from the front door, flow upstairs and found the room. It was even capable of doing the path in reverse so it could come in and out of my room.

I closed all the doors and windows on the first floor, but forget to close the small bathroom window. This was enough for the small wasp map an entire new path to my room again almost immediately!

Once it entered my room again, I opened the window again. It was smart enough to use it like it was simply choosing the shortest path.

So, even the small brain of a wasp is able to run "computer vision" algorithms and are fast running "machine learning" algorithms. They are even able to run A* perfectly and merge input from various sensors to perform superb navigation using very little energy, producing almost not heat in a very lightweight package in real time with very low latency!

I'm glad this critter is small. Nature is scary.

YeezyMode• 5 years ago

You may have already, but you'd enjoy reading 'Conscious Mind Resonant Brain' by Stephen Grossberg.

marcodiego5• 5 years ago

Thanks for the hint/tip/advice. Never heard about it. Hope you found my tone similar or with some close ideas.

jaclaz2• 5 years ago

What if I told you it wasn't the same wasp?

One wasp trasmitted a map of your house to another and another one!

marcodiego5• 5 years ago

Your comment may sound like a joke but bees are known to transmit direction and distance to one another and are also able to solve complex problems:

  https://www.popsci.com/science/article/2010-10/bees-beat-computers-ability-solve-complex-math-problem/

  https://en.wikipedia.org/wiki/Waggle_dance

tiborsaas• 5 years ago

Maybe it spoke with the same accent

apricot13• 5 years ago

genuinely thought the last line in this was going to be and then I found a wasps nest in the room next door!

not2b• 5 years ago

The wasp might be using smell to figure out the way into your house; any odor would come out of any open window.

dietr1ch• 5 years ago

It might be using A* then :P

Stratoscope• 5 years ago

Was it a paper wasp? They are so cute and friendly.

This little one didn't mind a bit when I put my macro lens an inch or two away, and even did some tricks to show off!

https://geary.smugmug.com/Macro/i-VsCPgMS/A

https://geary.smugmug.com/Macro/i-3xN7pMk/A

marcodiego5• 5 years ago

Can't tell, but looks similar.

jtms• 5 years ago

You might want to consider the “screen” algorithm :-)

Abishek_Muthian• 5 years ago

Could there be a wasp nest outside your window or worse inside your room?

KronisLV• 5 years ago

So, even the small brain of a wasp is able to run "computer vision" algorithms and are fast running "machine learning" algorithms.

Now i'm actually curious about its efficiency of the computation. If we could somehow map neurons to transistors (e.g. the logical calculations/algorithms, not the structure and not simulate neurons with transistors), which would be more efficient, the brain or the hardware?

csixty4• 5 years ago

Though they can, maybe cats are not designed to execute code after all?

I'll test this with my cat named Turing this weekend to see if he gives better results.

_Nat_• 5 years ago

It's apparent that the author of this article has independently discovered the field of Catputation. However, this field has a long and rich hissssstory, which I'll try to summarize as time allows (or until I'm bored or see something shiny).

FIRST: The great potential for Catputation has been recognized since pre-hisssstory, by the early innovators known as Egyptians who awed at the great possibilities and awww'd at the great paws-abilities.

In those days, Catputers were primarily used to perform primitive functions, such as alerting household members of impending dawn (known to those in the field as "the early-morning zooomies") and high-frequency generation before electronic-oscillators were discovered (known to those in the field as "ddawww, the widdle kittdy is purrrring!").

Unfortunately, Catputation was limited in those days to largely clumsy, analog tasks. For example, Catputers had difficulty playing nicely with some peripheral systems, e.g. mice. It wasn't until much later that [the first digital-logic gate was invented, allegedly by Isaac Newton](https://en.wikipedia.org/wiki/Pet_door#History), paving the way for more advanced systems.

However, as we all know today, cats are fundamentally clawtum-mechanical creatures.

Early on in clawtum-mechanical discovery, [Bose and Einstein were studying Dogputation](https://en.wikipedia.org/wiki/Bose%E2%80%93Einstein_statisti...). Dogputers have quanta which can share the same space, [forming a stack](https://en.wiktionary.org/wiki/dogpile) (known to those versed in the art as "dawwwww, look at dey widdle puppehs!"). This would later lead to [online-enthusiasts stockpiling Dogputation](https://en.wikipedia.org/wiki/Dogecoin).

However, in trying to form a stack for Catputation, Pauli made two simultaneous, serendipitous discoveries. First, they discovered that [kitties shouldn't be stacked up in the same place](https://en.wikipedia.org/wiki/Pauli_exclusion_principle). And secondly, that violating this newly-discovered rule can result in many little bytes forming a larger unit (a kill-0-byte). Together, these discoveries led to [an initial theory of clawtum-Catputation](https://en.wikipedia.org/wiki/Fermi%E2%80%93Dirac_statistics).

Progressing forward, optical computing became all the rage, and it was discovered that [optical-signaling interconnects were effective in facilitating high-speed Catputation](https://www.youtube.com/watch?v=aLagODygcbs).

There's more hisssstory to be told, though that's it for now!

s_dev• 5 years ago

Really did think this was the unix command 'cat' being Turing complete which makes sense.

carabiner• 5 years ago

Why do programmers like cats so much?

praptak3• 5 years ago

The null hypothesis here is that everybody likes cats.

ludamad• 5 years ago

Indeed. Cats and dogs are part of endless marketing materials for a reason. They're as generic appeal as it goes (something something everyone loves babies)

poulsbohemian• 5 years ago

-- Easy maintenance. They need food and cuddles, but they don't need to be let out to potty ten times a day or require excess walks.

-- They have a remarkably complicated inner life. This appeals to creative types, who also often have a lot going on mentally.

-- They are conducive to the lifestyle, apart from wanting to stand on my keyboard. They will sit in the cat tree or on my lap for a long time, just wanting to be near. They will remind you when it's time to stand up and stretch.

freddiecoleman• 5 years ago

CATs are implemented in a turing complete language called Chialisp https://chialisp.com/docs/puzzles/cats/

teddyh• 5 years ago

Cats do not run optimal algorithms:

http://www.threepanelsoul.com/comic/on-a

rawling• 5 years ago

Wow, that took me on a quick tour from "hey, I remember when that comic was running" through "hey, that comic is running again" to "hey, turns out that comic never stopped running?"

Konohamaru2• 5 years ago

Cats aren't Turing complete because they don't have intentionality. Everything it was doing was a result of instinct.

visarga• 5 years ago

Not much gap between instinct and intention. You could say instincts are default intentions selected by evolution.

ilyagr• 5 years ago

You might argue that animals don't have intentions (especially if you never observed one closely). However, it seems difficult indeed to believe that a cat has less intentionality than an abstract Turing machine -- or your desktop computer for that matter.

Konohamaru2• 5 years ago

Actual Turing machines (okay, finite state approximations of them, which are the only ones that can physically exist...) have externally imposed intentionality.

matbatt38• 5 years ago

Cats aren't Turing complete because they don't have intentionality. Everything it was doing was a result of instinct.

Well, first, cats most likely do have intentionality. But mostly, why do you think intentionality is a requirement for Turing Completeness ?

berkes2• 5 years ago

one of the best ways to avoid misuses of a feature is to perform these misuses once, in my opinion

I love this, because I'm convinced this is how we all learn.

How my cats learn too, by the way. Good thing they have nine lives, because the amount of pans, doors, cupboards, firewood that has fallen on top of them just for the sake of "I want to know if I can misuse this new pile" is staggering.

bitwize• 5 years ago

That cat looks a lot like my Ashley, who died nearly 14 years ago but is still missed. White chest patch, white toe tips, and all.

kzrdude• 5 years ago

Does it have an infinite tape?

blamestross2• 5 years ago

People keep forgetting you need infinite memory to be Turing complete. On a machine with finite memory, all operations are O(1).

k__• 5 years ago

All operations are O(1)?

tomcatfish• 5 years ago

Almost, but there are examples of non-termination still unless I am misremembering a definition (ex 20 GOTO 10).

cyounkins• 5 years ago

Honestly horses and carts are pretty good autonomous vehicles.

nyx_land• 5 years ago

I'll believe a cat is Turing complete when someone ports Doom to a cat

Is my cat Turing-complete?

Related Stories