Write a program for symbols valid for this machines

Assignment Help Other Subject
Reference no: EM131912124

History and Philosophy of Computing Universal Turing Machine

Exercise 1 Define a program ADD for the following:

- It starts reading the entries of a list of 0s and 1s one by one
- When it reads 0 does nothing on the input and moves right staying in
- When it reads 1 does nothing on the input and moves right staying in
- When it reads empty does nothing on the input and moves left and goes into Add state
- In Add state, when it reads 0 writes 1 and stays where it is and ends
- In Add state, when it reads 1 writes 0 and goes left and stays in Add state
- When it reads empty it writes 1 and stays where it is and ends.

What does this program do to a binary number? What to a list of 1s? what to an empty tape?

Exercise 2 Define a program ADD1 performing ADD separately on two binary numbers on the same tape, separated by *.

Exercise 3 Now define a program that takes a list of 1s and 2s and returns a sorted list with all 1s before all 2s. To do so, implement the following logic:

- the input of the machine is a list of 1s and 2s;

- first read the input from left to right
if there is a 1, keep it
as soon as you find a 2, change it to a placeholder for example 3, and move until the right end of the input

- when reached the right end, read the input from right to left
if there is a 2, keep it (and stay in this state)

if there is a 1, change it to 2, then go until the end of the input keeping everything as it is, except when you find a 3 change it into a 1 and then start again
if there is a 3 change it to 2, then move left until the first empty cell, and stop.

Note that the above description is very informal and not as detailed as the other ones. You have to figure out how many states are needed and how and when to change from state to state.

Exercise 4 Write a program for the following:
- the symbols valid for this machines are 1, 0,*
- the input is of the form r(1s * 1s)
- the machine subtracts the second series of 1s from the first

- the output is of the form r(1s0s*0s), where the list of 1s is the reminder of the subtraction, the 0s are the elements deleted respectively in the first and in the second input.

Exercise 5 Read the article by Copeland and Sommaruga (you will need to read at least sections 1, 3, 4). Explain the difference between the concept of stored-program in the theoretical sense of Turing and specify which term was used by Turing to express the notion of ‘program'. Moreover, highlights some of the other contributions to the development of this concept.

Exercise 6 Explain in which sense the development of the UTM justifies the Church-Turing thesis.

Reference no: EM131912124

Questions Cloud

Discuss the social issue or problem for exploration : Share the social issue or problem you chose (or are considering) for exploration in your Final Essay. Explain why you chose the social issue or problem.
Locate a recent article on cyber-crime : Locate a recent article on cyber-crime (within 6mo) and post the link for others.
Using unrealistic estimates for effort and duration : Please describe the following scheduling problems and give examples of them in relation to software projects.
Developing your own personal theory on leadership : Write a 3-page paper developing your own personal theory on leadership, including the answers to several questions (to be posted).
Write a program for symbols valid for this machines : CSD3203 – History and Philosophy of Computing Universal Turing Machine - Explain in which sense the development of the UTM justifies the Church-Turing thesis
Program written using kernel-level threads : If the program comprises 48 threads and is executed on an 6-processor system, what is the maximum possible speedup? Briefly explain your answer.
Code a python program : Need assistance with python. The question is: Summary: code a python program that demonstrates
How the pope has worked with the leaders of your faith : You may look at this through the lens of your own religious background and discuss how the Pope has worked with the leaders of your faith.
Which language do you speak at home or with your family : Which language do you speak at home or with your family? What were your goals/motivations when you came to Miami?

Reviews

Write a Review

Other Subject Questions & Answers

  Cross-cultural opportunities and conflicts in canada

Short Paper on Cross-cultural Opportunities and Conflicts in Canada.

  Sociology theory questions

Sociology are very fundamental in nature. Role strain and role constraint speak about the duties and responsibilities of the roles of people in society or in a group. A short theory about Darwin and Moths is also answered.

  A book review on unfaithful angels

This review will help the reader understand the social work profession through different concepts giving the glimpse of why the social work profession might have drifted away from its original purpose of serving the poor.

  Disorder paper: schizophrenia

Schizophrenia does not really have just one single cause. It is a possibility that this disorder could be inherited but not all doctors are sure.

  Individual assignment: two models handout and rubric

Individual Assignment : Two Models Handout and Rubric,    This paper will allow you to understand and evaluate two vastly different organizational models and to effectively communicate their differences.

  Developing strategic intent for toyota

The following report includes the description about the organization, its strategies, industry analysis in which it operates and its position in the industry.

  Gasoline powered passenger vehicles

In this study, we examine how gasoline price volatility and income of the consumers impacts consumer's demand for gasoline.

  An aspect of poverty in canada

Economics thesis undergrad 4th year paper to write. it should be about 22 pages in length, literature review, economic analysis and then data or cost benefit analysis.

  Ngn customer satisfaction qos indicator for 3g services

The paper aims to highlight the global trends in countries and regions where 3G has already been introduced and propose an implementation plan to the telecom operators of developing countries.

  Prepare a power point presentation

Prepare the power point presentation for the case: Santa Fe Independent School District

  Information literacy is important in this environment

Information literacy is critically important in this contemporary environment

  Associative property of multiplication

Write a definition for associative property of multiplication.

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd