CODEWITHSUNDEEP
logicstate-machineautomatacomputation-theoryturing-machines
Kieran Anderson
Kieran Anderson

Reputation: 29

Constructing a Turing Machine that deletes every second input symbol and then merges remaining string into a string with no blank gaps

While drawing a state diagram for this problem, I am confused by how to merge the input symbols. I have seen others demonstrate how to concatenate when the alphabet consists of one symbol, however, in my case, I have to check if I am copying either a 1 or 0 to the left while removing gaps.

Upvotes: 2

Views: 756

Answers (2)

trincot
trincot

Reputation: 349908

To get the desired output you could "move" the symbols at even indices to a separate section (separated by a blank) after the input, and delete the input as you do this.

But in your question you actually describe an algorithm that performs these actions:

  • Delete the symbols at odd indices
  • "Pack" the remaining symbols together

I have to check if I am copying either a 1 or 0 to the left while removing gaps.

This distinction has to be made via distinct states, so that the state "carries" the knowledge of whether the symbol to be moved is a 0 or a 1.

I would suggest not to perform all the deletions first and only then perform the moves. Instead I'd do both in one pass: perform the move of a digit to the left as soon as you have deleted the symbol that preceded it.

When you "move" a symbol to the left, leave exactly one blank in its stead. If the distance of the move is more than one spot, then fill the other spots with a (temporary) digit. On the way back to the right these are replaced by blanks, but it allows you to recognise when all input has been processed (more than one successive blank is encountered).

Here is a transition table for that algorithm ("_" is the blank):

state read write move head next state
start 0 or 1 right delete
delete 0 or 1 _ right keep
delete _ left halt
keep 0 _ left keep0
keep 1 _ left keep1
keep _ left halt
keep0 _ 0 left fill0
fill0 _ 0 left fill0
fill0 0 or 1 right skip
skip 0 or 1 right clear
clear 0 or 1 _ right clear
clear _ right delete
keep1 _ 1 left fill1
fill1 _ 1 left fill1
fill1 0 or 1 right skip

And here is a snippet to run it with your input of choice:

createTuring({
    transitions: [
        { state: "start",      read: "01",             move: "R", nextState: "delete"    },
        { state: "delete",     read: "01", write: "_", move: "R", nextState: "keep"      },
        { state: "delete",     read: "_",              move: "L", nextState: "halt"      },
        { state: "keep",       read: "0",  write: "_", move: "L", nextState: "keep0"     },
        { state: "keep",       read: "1",  write: "_", move: "L", nextState: "keep1"     },
        { state: "keep",       read: "_",              move: "L", nextState: "halt"      },
        { state: "keep0",      read: "_",  write: "0", move: "L", nextState: "fill0"     },
        { state: "fill0",      read: "_",  write: "0", move: "L", nextState: "fill0"     },
        { state: "fill0",      read: "01",             move: "R", nextState: "skip"      },
        { state: "skip",       read: "01",             move: "R", nextState: "clear"     },
        { state: "clear",      read: "01", write: "_", move: "R", nextState: "clear"     },
        { state: "clear",      read: "_",              move: "R", nextState: "delete"    },
        { state: "keep1",      read: "_",  write: "1", move: "L", nextState: "fill1"     },
        { state: "fill1",      read: "_",  write: "1", move: "L", nextState: "fill1"     },
        { state: "fill1",      read: "01",             move: "R", nextState: "skip"      },
    ],
    initState: "start",
    tape: "1110110111101101",
});
<script src="https://trincot.github.io/turing.js"></script>

Upvotes: 0

Kieran Anderson
Kieran Anderson

Reputation: 29

Here, there is mention of a multi tape turing machine but it only partly explains how a solution may exist for my problem: https://en.wikipedia.org/wiki/Multitape_Turing_machine#Two-stack_Turing_machine

Upvotes: -1

Related Questions