81–89 of 89 posts
Earlier quoted context omitted.
Well, really, it's what happen when you make an impression at Hack and Tell ( http://hackandtell.org )! This was perhaps the highlight of last night's Meetup.
Thats a cool premise for a meetup. Wish there was one in Seattle.
Way to steal my karma.... :) As the original author of this, I was going to put it into a much more presentable state before showing it off here. For those confused, here's a proper explanation. No real-world thing can actually be Turing complete (able to express basically any computation that we might want to perform of any size). That's because there are finitely many atoms in the universe, so we can only construct…
That's what happens when you put something on github! In fact, I bet you any money that someone has already taken the code and created a 16-bit logic unit INSIDE minecraft INSIDE your turing machine.
Earlier quoted context omitted.
> No real-world thing can actually be Turing complete But when you say Turing-complete, I assume something along the lines of "a programming language can be built on top of it and you can create interactive applications using such a programming language instead of javascript". It seems like that's not the case at all.
Everyone's being a little cagey about what Turing Completeness really means, in layman's terms, because I think the assumption is that if you're here, you should already have a deep understanding of it. So no, as others have said, you are completely off base as to what the significance of being Turing complete is. What Turing complete means is that given an infinite amount of memory and time, a language can simulate…
Earlier quoted context omitted.
Nope. The common usefulness is to determine whether a given computation-describing system reaches the threshold of universal computability. Modulo finite size is assumed, else there is no usefulness of the concept given finite resources. For example, SKI combinators are Turing-equivalent. Regular expressions aren't. The lambda-calculus is. Context-independent grammars probably are. Most data description languages are…
>Context-independent grammars probably are. No they are not. Recursively Enumerable grammars are however. A context free grammar can't be turning complete because it can be decided with only a PDA.
Earlier quoted context omitted.
you forgot to mention that the turing machine runs in a browser that runs in another turing machine which is inside a huge machine called the universe.
inside a dream, inside another dream!
Earlier quoted context omitted.
> However, if I can choose a large enough regex, I can construct a decider for a given finite language. What do you mean by this? What is a "decider"? What do you mean by a finite language?
Language: http://en.wikipedia.org/wiki/Formal_language Decision problem: http://en.wikipedia.org/wiki/Decision_problem Decider: http://en.wikipedia.org/wiki/Machine_that_always_halts These are fairly foundational concepts when talking about computational complexity.
Ok so upon reflection I think I see what you are getting at. Practical computers are have limited memory and so are, in principle, equivalent to a finite state machine.
So anything a practical computer can do a, perhaps ridiculously large, regular expression can also do?
Is that close?
Earlier quoted context omitted.
Well, really, it's what happen when you make an impression at Hack and Tell ( http://hackandtell.org )! This was perhaps the highlight of last night's Meetup.
Thats a cool premise for a meetup. Wish there was one in Seattle.
Earlier quoted context omitted.
But what's in that string? That still counts. What I should have done was put an additional restriction on what IO is available. Otherwise, something like "eval `cat f`" or something could be all powerful. My first attempt shows Ruby simulating a cyclic tag system with only 15 unique characters including newlines and spaces: https://github.com/elitheeli/oddities/raw/master/only_a_few_... EDIT: down to 14 characters.
"But what's in that string? That still counts." Sure, but it counts regardless of what you're talking about. We don't generally talk about charging data against the TM because they all need data of some sort to do anything interesting. "eval" still gets you there. (Pedantic.)