Comp Sci What Is Dovetailing Technique in Turing Machines?

[shivajikobardan]

Homework Statement

Explain dovetailing technique with suitable example

Relevant Equations

None

I have collected some information related to it. It seems like it is basically doing stuffs in parallel. But I am not 100% clear about what it really means.
Here is some information I've about it. But it doesn't really makes a lot of sense to me.

Source-: https://www.utsc.utoronto.ca/~bretscher/c63/lectures/w3_printable.pdf

can you help me figure this out? what is dovetailing? in simple words with an example?

 

[shivajikobardan]

So I found out something. But I've confusions at the conclusion of it.

https://gateoverflow.in/235651/Toc-dovetailing
I have 2 confusions from it-:(I clicked it to preserve formatting) The first one is this. How does this really work?

At last it explains how infinite loop doesn't occur here, I don't understand that point. It writes

"Thus due to this method if for any string the TM would have gone into infinite loop for a single TM arrangement, here, due to simultaneous step by step arrangement, we don not encounter this problem because for those strings(infinite loop one),we go to the next step of execution and simultaneously we check for other valid strings in other TMs".

Like how can there be no infinite loops. 10000 turing machine, 10000 words/strings. If any string leads to blocking state, then still infinite loop will occur in that particular machine, isn't it? What am I missing here?

Also is the above question details that I posted related anyhow to this example?

 

[FactChecker]

It's just a way of interleaving (dovetailing) any number of infinite lists, $J_{i,j}$, so that each list is done, even if there are an infinite number of lists.
I do not understand what the link in your second post is saying, but I think the first post is fairly clear.

 

[shivajikobardan]

It's just a way of interleaving (dovetailing) any number of infinite lists, $J_{i,j}$, so that each list is done, even if there are an infinite number of lists.
I do not understand what the link in your second post is saying, but I think the first post is fairly clear.

ah i see. thanks a lot for confirming, stackexchange said otherwise so i got confused.

https://cs.stackexchange.com/questions/64264/dovetailing-in-turing-machines

. i am bit rusty with programming atm. can you explain what that last slide of my original post meant?

 

[FactChecker]

. i am bit rusty with programming atm. can you explain what that last slide of my original post meant?

If you have an infinite number of infinite lists, you do not want to address all of the infinite number of lists at once. Instead, you only include a finite number on each iteration of the outer loop and do one more on the next iteration.

 

[Mark44]

It helps to know that "dovetail" is a term used by woodworkers for a joint that connects two pieces of wood.

In the context of this thread, instead of different pieces of wood being interleaved, your study materials are describing tasks being interleaved.

 

[pbuk]

If it helps, the answer in this post is nonsense (it talks about 10,000 threads on 10,000 parallel Turing machines: this is nothing to do with dovetailing).

https://gateoverflow.in/235651/Toc-dovetailing

And contrary to what you said:

stackexchange said otherwise
https://cs.stackexchange.com/questions/64264/dovetailing-in-turing-machines

the (main) answer in that SE thread correctly confirms the information in your original post.

Put simply, dovetailing is a method of working on multiple tasks at once. If you only have two tasks, this is easy:
$$ t_{0, 0}, t_{1, 0}, t_{0, 1}, t_{1, 1}, \dots $$
With $n$ tasks it is still easy
$$ t_{0, 0}, t_{1, 0}, \dots, t_{n, 0}, t_{0, 1}, t_{1, 1}, \dots, t_{n, 1}, t_{0, 2} \dots $$
and that is all you need to know about dovetailing in practice.

Note that in theory you can handle an infinite number of tasks such that however large you make $i$ and $j$ you will always reach stage $j$ of task $i$ in finite time:
$$ t_{0, 0}, t_{1, 0}, t_{0, 1}, t_{2, 0}, t_{1, 1}, t_{0, 2}, t_{3, 0} \dots $$
The concepts of Hilbert's Hotel and Cantor Diagonalization are useful background to this and other important aspects of the theory of computation.

 

[Jarvis323]

ah i see. thanks a lot for confirming, stackexchange said otherwise so i got confused.

https://cs.stackexchange.com/questions/64264/dovetailing-in-turing-machines

. i am bit rusty with programming atm. can you explain what that last slide of my original post meant?

The answer there doesn't say otherwise, they are just describing dovetailing in the context of enumerating Turing recognizable languages. You need to understand Turing recognizable languages (or recursively enumerable languages), enumerator Turing machines, and languages of Turing machines. It's probably important to understand this because your course will probably build on these concepts later on.

A language is a set of finite strings. The set of strings that a Turing machine $M$ accepts is called the language of the Turing machine, or $L(M)$. If a language $L_a$ is Turing recogniable or equivalently recursively enumerable (RE), it means there is some machine $M$ such that $L_a=L(M)$, i.e. there is an $M$ that halts on an accept state for every string in $L_a$ (whereas it isn't required that it also rejects / halts on reject states for strings it doesn't accept).

So suppose you want to create a Turing machine that enumerates a language, $L(M)$, you could simulate $M$ on candidate strings counting up by 1, e.g. 0, 01, 10, 11, ... Then, if the Turing machine accepts the string, it means it will land on an accept state and halt, and then the enumerator should print the string. But $M$ might not halt for some input string that it doesn't accept. It might diverge and go on forever without every telling you if it will accept the string. So if you tried going over each possible string one by one and checking if $M$ accepts it, you might get stuck forever checking some input and be unable to advance to check if it accepts the next one. The solution is dovetailing. In that case, what you do is that instead of running the Turing machine to completion for one input and then moving on to the next, you do this one neat trick. Here is an example how you can implement it using dovetailing.

    # takes a Turing machine as input and enumerates its language
    def enumerate_language_of( M ):
       simulations = []
        for i = 0 to infinity:
            # start a new simulation
            simulations.push( simulation that runs M on input i )
            # advance all of the ongoing simulations by one step
            for j = 0 to i:
                advance_one_step( simulations[ j ] )
                if simulations[ j ] landed on accept state:
                    print( j )

It's also the case that something like the above is equivalent to parallelism as far as computability is concerned. So you might hear it explained that way instead, especially in the context of non-deterministic Turing machines.

Technically an enumerator is allowed to repeat strings as well. So you might also see something like below in some texts:

    # takes a Turing machine as input and enumerates its language
    def enumerate_language_of( M ):
        for i = 0 to infinity:
            for j = 0 to i:
                run M on input j for i steps
                if M has accepted j:
                    print( j )

Which will repeat strings, but ... who cares I guess.

Below is the version which doesn't work, because $M$ might not halt on some input $x$ and because HALT is not decidable, you could be stuck running $M$ forever without knowing if it will accept $x$ or not.

    # takes a Turing machine as input and enumerates its language
    def faulty_enumerator( M ):
        for i = 0 to infinity:
            run M on input i
            # what if M doesn't halt on input i? Then we wait forever.
            if M accepted input i:
                print( i )

There are also co-recursively enumerable (co-RE) languages (co stands for compliment). A co-RE language $L$ is a set of strings for which there exists a machine M such that M halts on a reject state for all strings that are NOT in $L$. So if run on a string not in $L$, it will always halt and tell you the string was rejected. But if the string is in $L$, it might keep you waiting forever without giving back any answer.

Then finally, there are decidable languages, which are both RE and co-RE. This means there is a machine $M$ such that M will halt on $x$ and reject if $x \notin L$ and it will halt on $x$ and accept if $x \in L$. For a decidable language, you can enumerate it without needing dovetailing, and the reason is that it always halts.

Where this is all heading is that decision problems are formalized as languages, where each string in the language is one yes instance of the problem. E.g. HALT is a language (set of strings), where each string in the set is an encoding of a program and input $<p,x>$, such that $p$ halts on input $x$. And HALT is RE but not co-RE, and thus is not decidable, but you can enumerate it, i.e. you can create a Turing machine that will print out all of the (program, input) pairs where the program halts on the input. That enumerator needs to use dovetailing of course.

Then there are languages which are neither RE nor co-RE. No dovetailing can help you there. You wouldn't be able to list the strings in the language or the strings not in the language.

Previously I've been saying a language (or problem) can be RE or co-RE. But you will see RE and co-RE described as sets of languages/problems. E.g. $HALT \in \text{RE} \wedge HALT \notin \text{co-RE}$, and $DECIDABLE = \text{RE} \cap \text{co-RE}$