A Small Riddle
Imagine I have a bucket with an infinite number of dominoes. Each domino looks like one of these:
In other words, I have an infinite number of dominoes which read “a” at the top and “baa” at the bottom, and so on for the other types. The dominoes can’t be turned end for end: they have a specific top and bottom (otherwise the letters would be upside down, which is obviously crazy).
Here’s the riddle: try to arrange the dominoes, in any order you like, so that the string made of all the tops of the dominoes and the string made of all the bottoms of the dominoes is the same string.
The simplest attempt is to take one of each kind of domino and arrange them in order, as in the picture above. Reading all the tops of the dominoes gives the string “a,ab,bba”, and the bottoms read “baa,aa,bb”, which are obviously not the same string (I added the commas for clarity, but the comparison is done without them).
Is it possible to find an arrangement with those three types dominoes to get an answer? The solution, in this case, is the following:
If we number the original dominoes 1-3, this solution has the sequence: 3-2-3-1, and the strings read: “bba,ab,bba,a” and “bb,aa,bb,baa”. Without the commas, both strings read: “bbaabbbaa”. Not too difficult.
The General Problem
Now comes the interesting part. I could ask you the same question, but give you a different set of dominoes. For example, I could give you the same set as before, but without the third domino:
It’s pretty clear that in this case, no solution is possible. If I start with the first domino, already the strings are different, since one starts with an “a” and the other with a “b”. Likewise, starting with the second domino gives us a top string that starts “ab” and a bottom string that starts “aa”, so once again, we are stuck.
So the general question becomes, given a set of dominoes, is there a way to solve the problem by forming two equal strings? In other words:
Given a set of domino types, return True if the problem can be solved (i.e., the dominoes can be arranged to form two equal strings), or False otherwise.
Take a few minutes to try and come up with the algorithm that solves this. But don’t try for too long; this is a deceptively difficult problem.
The Solution
Okay, I lied a little. This isn’t a difficult problem; it’s an impossible one. There is no possible algorithm which solves the general case of the Correspondence Problem, as was proved by Emil Post in 1946.
The proof of the undecidability of the Post Correspondence Problem is a complicated one. I learned it from Sipser’s Introduction to the Theory of Computation
Why I love the Post Correspondence Problem
I love the field of Computer Science, and I really love questions about decidability. It seems magical to me that some problems can never be solved by an algorithm. But most of the time, the undecidable problems (like the famous Halting Problem), seem a little detached from actual programming.
The reason I love the Post Correspondence Problem is that this seems like it should have an answer. When I first heard about it, I spent a lot of time looking for an algorithm to solve this, before learning that no algorithm can exist. This is the type of problem I can imagine running into during my day to day programming, and trying to solve it without realizing that it can’t be solved.
Which leads me to wonder: how many times have programmers working on real-life programs stumbled onto unsolvable problems, and tried to attack them without realizing the futility?
{ 15 comments… read them below or add one }
Actually, I think the halting problem is very attached to actual programming. You could ask yourself: “Can I write a program which will decide if this other program terminates?”
I love Sipser’s book, too, by the way.
While there is a class of programs that may be undecidable in the general case, it is quite often the case that extra constraints can be put on the problem making it algorithmically tractable in that particular situation. You can also bound an algorithm’s search so attacking subsets of these problems may not be entirely futile.
A very nice problem.
But what if we limited the number of letters on each half of the tile.
(Say, to “n” where n is finite.)
And allowed an arbitrarily large but finite set of tiles to populate the
infinitely random bucket.
(That is, say there are exactly m different types of tiles.)
So if we set n and m beforehand would the problem still be undecidable?
Yes, n and m can become inputs to the algorithm but I think you’ll find
this one IS decidable!
(Hint. It’s equivalent to saying. “I can solve the Halting Problem
but only for programs less than 10^(10^10) bytes long on a known UTM.)
> ‘It’s equivalent to saying. “I can solve the Halting Problem but only for programs less than 10^(10^10) bytes long on a known UTM.’
Except that there’s still the question of what happens when you run that program on itself. Taking a step back, the Halting Problem posits a program which will terminate if its input fails to, and vice versa. That formulation is critical, because it means that whether the program terminates is *entirely dependent* upon its input – so when run upon itself, it simply doesn’t have the required information to determine termination… and it can never have, because no matter how many times you specify that program as its own input, it never has enough information to make that determination. You can only determine the termination of a program whose properties are all knowable in advance – in other words, a program which doesn’t accept a Turing-complete language as an input. Your 10^10^10 example does, and therefore remains inherently undecideable.
gwenhwyfaer: Nope, you’ve missed a critical point — your analysis assumes that the solution to the limited-space halting problem must also fit into the limited space, such that it actually makes sense to feed it to itself as input. There’s no such restriction. In particular, you have merely proved that it can’t fit there — but you haven’t proved that it’s impossible to have a “solution” program that, when run on itself, immediately terminates with a correct output of an error message: “this input program is longer than the limited space for which I can compute”.
More particularly, it would be possible to have a program that’s simply a boolean lookup table of size (2^8)^(10^(10^10)) — i.e., one entry for every program in the space. Such a program can obviously exist, and can be obviously posited to return a correct result for every program in that space.
Steve: Yes, the limited-number-of-tiles problem is trivially decidable; you can just enumerate all the possible tile orderings and check them.
I think you’ll also find that limiting the overall number of tiles (or even just limiting the number of different kinds of tiles) limits the number of letters, so that constraint is redundant. A single given tile cannot have infinite letters, by the definition of a tile, so the only way you can have an unlimited letter count is by having an infinite number of different kinds of tiles, such that a subset of those tiles form a diverging infinite sequence. (Of course, if they’re actually different, they have to do that.)
Let me throw something out for the really smart people to debunk here…
If we treat the domino as a fraction of factors composed of [a,b], then we see for the first solution that the dominoes reduce to the set: 1/ba, b/a, a/1. The question is can we multiple a combination of these together such that we get 1/1. Multiplying the first three together, we see that they equal 1/a. Since a/1 is in the set, we can multiple 4 together to get 1/1. So there is a solution. The problem is, due to the associative nature of multiplication, I don’t think I can guarantee that the strings are the same order top and bottom. Need to work on that.
However, the second problem, where the third domino is deleted, when reduced and multiplied together gets 1/aa, and since there is no a/1 in the set, there is no way to get to identity. Hence, there seems to be a way to declare that something definitely can not be solved.
I may be off base, but I thought I’d throw it out there. Need to explore more for the general case.
I love such “problems”. They only seem to be a problem for a select few. The others simply work a few days on a problem which is actually a “Post Correspondence Problem” , and then give up and have a few beers. Their solution to the problem is – “Chuck it”. The nerds at the lab keep breaking their head over it. In the end they are none the wiser !
I use to get into these algorithm “problems”, but that was before I realized such problems are mostly a waste of time if its not answering anything but an “academic question”.
Man in his infinite wisdom has created a set of rules called Math, and every now and then this framework leads us to a curious cul-de-sac. Some reach halfway, find the going tough – and then move on to the next avenue. However some of us don’t give up till they hit the stone wall at the end. The Post Correspondence Problem poses one such wall at the end of a long and difficult street. However much may it be proven, that there is a stone wall at the end, each generation nonetheless will have “those guys who want to keeping breaking their head against the wall !”
Actually, for those three dominoes in particular there might be a solution.
Forget for a second that you need to make the same string, and try to solve a smaller problem. The number of letters ‘a’ and ‘b’ on the top part of the domino must be the same as the one on the bottom in order to even have a chance of being the same string. So lets think about it.
bba/bb has the same number of ‘b’ on both sides but has one ‘a’ too many on top.
We can counter this.
ab/aa has one extra ‘a’ on the bottom to counter it, but there is also another extra ‘b’ on top.
We can counter this again.
a/baa has an extra ‘b’ on the bottom to counter it, but alas, there is an extra ‘a’ on the bottom again.
We can counter this yet again.
We can add another bba/bb, which has an extra ‘a’ on top, and now the number of ‘a’ is equal to the number of ‘b’ both on top and on the bottom, and this is the smallest set you can build with these characteristics.
This set is, actually, the one chosen by this article as an example of a string that matches both the top and the bottom, so all you have to do is check if a given number of dominoes has the right ratio of dominoes.
2 bba/bb for each ab/aa and each a/baa.
I once tried making a lookup table with (2^8)^(10^(10^10)) bits of information in the index but I ran out of atoms less than 1% of the way into the project.
Of course by then I was seriously over budget and entropy was starting to take over the hard work I’d already done.
:-)
@Mark
I seem to recall using a very similar method to show that the Post Correspondence Problem is decidable as long as the alphabet only has one character in it. (The blog post cites Sipser’s Introduction to the Theory of Computation; it’s exercise 5.17 in my 2nd edition copy)
I think you’re going to run into problems with extending that approach though – there doesn’t seem to be an easy way to deal with the ordering.
@Surajit Would you rather we not know?
@OP
I don’t think the proof of undecidability in Sipser requires an infinite number of types of dominoes, just an infinite supply of each type of domino.
@Alex – You’re right, you don’t need an infinite amount of types. Guess I didn’t make that clear in the article.
As I started to play with it, I started to see that only special cases would apply to a reduction like this. I was hoping to be able to prove that at least a set of dominoes could never work, but beyond the special cases intractability comes into play.
Thanks for something fun to think about! Without guys willing to beat their heads against perceived brick walls, lots of progress would be missed.
@Mark: Yes, the problem is that multiplication is commutative, so for example ba/ab would give you 1/1.
@Brooks: “A single given tile cannot have infinite letters, by the definition of a tile…” – you are confusing ‘unbounded’ with ‘infinite.’ True, a tile cannot have infinite letters, and any instance of the problem has a maximum number of letters-per-tile, but for any maximum for a given instance I can show you an instance where the maximum is greater than that. As Alex mentions above, the problem is decidable if we limit every tile to one letter on top/bottom; the question is, is it decidable if we limit the letters-per-tile to 2? 10? n?
Wish I’d seen this sooner.
“Nope, you’ve missed a critical point — your analysis assumes that the solution to the limited-space halting problem must also fit into the limited space, such that it actually makes sense to feed it to itself as input.”
If you can’t feed the checker to itself as input – that is, if your checker cannot accept arbitrary input – you can’t even *formulate* the Halting Problem, let alone claim to have solved it. The only languages which can be checked for decideability are incapable of expressing undecideable algorithms, *period*. This is a well-known result; your claim to the contrary, if supportable, would be original and startling, and I encourage you to start writing your dissertation on it.
{ 1 trackback }