Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

Universal Turing Machine In Penrose Tile Cellular Automata

Unknown Lamer posted about 2 years ago | from the mine-bitcoins-using-xscreensaver dept.

Math 24

New submitter submeta writes "Katsunobu Imai at Hiroshima University has figured out a way to construct a universal Turing machine using cellular automata in a Penrose tile universe. 'Tiles in the first state act as wires that transmit signals between the logic gates, with the signal itself consisting of either a 'front' or 'back' state. Four other states manage the redirecting of the signal within the logic gates, while the final state is simply an unused background to keep the various states separate.' He was not aware of the recent development of the Penrose glider, so he developed this alternative approach."

cancel ×


Sorry! There are no comments related to the filter you selected.

Woosh (-1)

Anonymous Coward | about 2 years ago | (#41193049)


Universal Turing Machines (2)

2.7182 (819680) | about 2 years ago | (#41195091)

There is a reason there are 50 different definitions of computable function - they are not hard to come by. As a professional mathematician/theoretical computer scientist I find it totally unsurprising to find one in the Penrose tiles. If it is useful for something, that's different. But you build almost any sufficiently rich mathematical structure and you can interpret a subset of them as Turing machines.

Re:Universal Turing Machines (0)

Anonymous Coward | about 2 years ago | (#41201877)

If you could characterize "sufficiently rich", that might be a more interesting observation.

Are there Penrose buckyballs? (1)

G3ckoG33k (647276) | about 2 years ago | (#41193153)

Are there Penrose "buckyballs", i.e. a version of the buckyball using the Penrose tiling?

I am not sure if they exist mathematically and have never seen them discussed anywhere.

Re:Are there Penrose buckyballs? (0)

Anonymous Coward | about 2 years ago | (#41193387)

Penrose tilings have negative curvature.
Balls have positive curvature.

They are opposites.

Re:Are there Penrose buckyballs? (0)

Anonymous Coward | about 2 years ago | (#41193481)

Penrose tilings have negative curvature.
Balls have positive curvature.

They are opposites.

But, what if you turn the tiling upside down? ;)

correction (0)

Anonymous Coward | about 2 years ago | (#41194085)

Um, I mean, Penrose tilings have zero curvature. I was thinking of thinking of the Poincare disc. Sorry.

Re:Are there Penrose buckyballs? (1)

Hentes (2461350) | about 2 years ago | (#41193553)

Penrose tilings are flat, hence they can't cover a ball. It's impossible [] .

Re:Are there Penrose buckyballs? (0)

Anonymous Coward | about 2 years ago | (#41193739)

Hexagons are flat too...

Re:Are there Penrose buckyballs? (1)

NoNonAlphaCharsHere (2201864) | about 2 years ago | (#41193885)

Soccer balls are not regular polyhedrons. Nor are they spheres.

Re:Are there Penrose buckyballs? (0)

Anonymous Coward | about 2 years ago | (#41201909)

Buckyball surfaces are a mix of hexagons and pentagons. It's the pentagons that allow the ball to be non-flat.

Re:Are there Penrose buckyballs? (1)

Mikkeles (698461) | about 2 years ago | (#41194847)

True, but it be interesting to know if a sphere could be "triangulated" with Penrose tiles.

Re:Are there Penrose buckyballs? (4, Interesting)

Anonymous Coward | about 2 years ago | (#41193605)

No, you can't make a sphere with Penrose tiling. As has already been mentioned, a flat tile can't be used to cover a sphere. But more importantly, there isn't a generalization that will work either. The thing that makes Penrose tiling interesting is that it is aperiodic. No aperiodic pattern can work on a sphere since you necessarily are periodic when you make one complete revolution around any greater circle on a sphere.

Permutation City (4, Interesting)

Shad0w99 (807661) | about 2 years ago | (#41193407)

Somehow Greg Egan's book "Permutation City" came to my mind when reading this. With his Autoverse representation on cellular automats.

Re:Permutation City (1)

blackpaw (240313) | about 2 years ago | (#41196869)

Or "diaspora" where I belive he had naturally occurring penrose tiles in an alien biology performing turing calculations

Re:Permutation City (1)

mrsurb (1484303) | about 2 years ago | (#41222431)

His short story "Wang's Carpets" - which then became a chapter in "Diaspora"

Turing Machines Everywhere (-1)

Anonymous Coward | about 2 years ago | (#41193409)

Is this another Minecraft story?

8 states? (1)

Hentes (2461350) | about 2 years ago | (#41193507)

That's not very impressive, especially since he basically just copied the four-state WireWorld rule.

There you go (1)

dargaud (518470) | about 2 years ago | (#41194575)

Previous /. story [] : "Before we can totally discount the theory that space-time is comprised of Planck-scale pixels, [...]". There you go, you can have Penrose-tiled planck pixels and still move in straight lines. Where do I pick my Nobel ?

What's a Turing Machine? (-1)

Anonymous Coward | about 2 years ago | (#41194859)

One that can buttfuck as well as a human?

Re:What's a Turing Machine? (-1)

Anonymous Coward | about 2 years ago | (#41195831)

Awwww, me got downmodded....

Re:What's a Turing Machine? (-1)

Anonymous Coward | about 2 years ago | (#41199907)

It wasn't funny. Alan Turing's suicide over his socially unaccepted homosexuality was a loss to us all.

Impressive (0)

Anonymous Coward | about a year ago | (#41204661)

Wow !

Is this a New Kind of Science?

Thanks for posting this story! (0)

EnergyScholar (801915) | about a year ago | (#41206459)

I wish to offer a general apology for the terrible quality of comments on this story. Obviously, most readers failed to even understand what the story was about. I thought the best comment was the snarky 'Is this NKS?' at the end, as this story obviously does tie into NKS. Anyway, thanks, submeta, for posting a fine old skool slashdot story. Let's hope our readership is less ignorant and juvenile next time around.
Check for New Comments
Slashdot Login

Need an Account?

Forgot your password?
or Connect with...

Don't worry, we never post anything without your permission.

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>