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.

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

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:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of