read and write head which traverses along the tape, capable of reading the current cell, writing a new value in the current cell, and moving left or right.C Programming

Differentiate between characters representing numbers (e.g., '1') and numbers themselves

It has infinite tape, divided into cells

  • A read/write head which traverses along the tape, capable of reading the current cell, writing a new value in the current cell, and moving left or right
  • A state register
  • A finite table of instructions which, given the current state of the machine, and the value in the tape cell currently being read, retrieves an instruction which tells the machine to:
  1. Write some (possibly the same) item into the cell
  2. Move the head left or right one cell
  3. Change to some (possibly the same) state

Its one way infinite to the right with starting character A and A can be used somewhere else.

TM tape is made up of cells. Computationally, represent the tape as a linked data structure of cells, wherein a cell (most conveniently represented as a struct) has a character representing what is written in that cell of the tape, and pointers to previous and next cells.

The initial contents of the tape (to be written immediately after the 'A' cell) will be provided by an input file. Your program should allocate just enough cells for the input. If you need more cells during processing you should create new blank cells on the fly. We'll establish the convention that a tape cell containing the character 'B' is a blank cell.

The read/write head of your TM should be a pointer to some cell of the tape. Begin machine execution with the read/write head pointing to the leftmost cell on the tape (the 'A'). As you move the read/write head, you will update the pointer to the current cell seen by the read/write head.

 

The set of instructions will be provided in the input file in the form: (CurrentState,ReadVal)->(WriteVal,MoveDirection,NewState). The first pair represents a configuration of the machine wherein an instruction, the triple after the arrow, should be executed.

In order to represent the instruction table in your program, make two- dimensional array, where the row indices are states and the columns indices are all standard ASCII characters which may be read from or written to the tape (i.e., there should always be 128 columns, representing ASCII

0-127). Given the current state and the current character being read by the read/write head, the machine looks up an instruction in this array. For example, if the machine is in state 1, reading a 'B' from the tape it should access [1]['B'] in the array. The instruction at that position will tell the machine what value to write, what direction to move, and what the new state should be.

Example below, this would be to "write" a 'B', move left, and change to state 2).

Below is a sample input file which adds two unary numbers together. Given an initial tape input of 111B1111, representing the numbers 3 and 4 separated by a blank, the machine walks to the end of the tape, changing the middle B to a 1, and changing the last 1 to a B. The result is 1111111, unary 7. The program assumes the machine starts at the beginning of the tape (on the 'A' cell).

The input file has the following specification:

Line 1: Initial tape content (written after 'A' cell) Line 2: Number of states

Line 3: Start state Line 4: End state

Remaining lines represent the state machine.

 

Each line is has 5 parts:

(CurrentState,ReadVal)->(WriteVal,MoveDirection,NewState)

remember that your program should work for any input file which represents a Turing Machine in this format, with any number of states. Your program should begin by asking for a filename for a TM from the user, which it should then load. The TM should then immediately begin execution.

Given the above input file, the program should result in unary 7, with a couple blank cells after the result. My version produces the following: Input file: input_test_1

Writing tape...

Initial tape contents: A111B1111 Final tape contents: A11111

Attachments:

Instructions Files

C Programming Experts

expert
Arapera Billing
C Programming

89 Answers

expert
Simon M.
C Programming

44 Answers

View More Experts
Disclaimer

The ready solutions purchased from Library are already used solutions. Please do not submit them directly as it may lead to plagiarism. Once paid, the solution file download link will be sent to your provided email. Please either use them for learning purpose or re-write them in your own language. In case if you haven't get the email, do let us know via chat support.

Get Free Quote!

259 Experts Online