subject
Engineering, 04.11.2019 22:31 Isaiahtate053

Let even = {hm, xi | m is a turing machine that runs on input x for an even number of steps}. of course, a turing machine running for infinitely many steps neither runs for an odd nor an even number of steps. we want to show that even is undecidable by a proof from scratch (i. e., by diagonalization not by a reduction). first we assume even is decidable, i. e., there is a tm h that accepts hm, xi if m is a turing machine that runs on input x for an even number of steps, and rejects otherwise. we want to do the diagonalization in two stages.

(a) first, describe a tm d˜ (based on the supposedly existing tm h) accepting hmi if and only if m is a turing machine that runs on input hmi for an even number of steps. otherwise d˜ rejects. note that you may assume the correctness of the church-turing thesis, i. e., instead of describing a turing machine in detail, you can just describe an algorithm in pseudo–code.

(b) now define a tm d from d˜ that runs on hmi for an odd number of steps if d˜ accepts hmi. otherwise d runs for an even number of steps.

(c) how does the existence of this produce a contradiction?

(d) what does the contradiction prove?

ansver
Answers: 1

Other questions on the subject: Engineering

image
Engineering, 04.07.2019 18:10, alyssabailey7545
Give heat transfer applications for the following, (i) gas turbines (propulsion) ) gas turbines (power generation). (iii) steam turbines. (iv) combined heat and power (chp). (v) automotive engines
Answers: 1
image
Engineering, 04.07.2019 18:10, agpraga23ovv65c
Carbon dioxide gas expands isotherm a turbine from 1 mpa, 500 k at 200 kpa. assuming the ideal gas model and neglecting the kinetic and potential energies, determine the change in entropy, heat transfer and work for each kilogram of co2.
Answers: 2
image
Engineering, 04.07.2019 18:10, juansoto227711
Journeyman training is usually related (clo2) a)-to specific tasks b)-to cost analysis of maintenance task c)-to control process to ensure quality d)-to installation of machinery
Answers: 2
image
Engineering, 04.07.2019 18:10, QueenLife4869
Awall of 0.5m thickness is to be constructed from a material which has average thermal conductivity of 1.4 w/mk. the wall is to be insulated with a material having an average thermal conductivity of 0.35 w/mk so that heat loss per square meter shall not exceed 1450 w. assume inner wall surface temperature of 1200°c and outer surface temperature of the insulation to be 15°c. calculate the thickness of insulation required.
Answers: 3
You know the right answer?
Let even = {hm, xi | m is a turing machine that runs on input x for an even number of steps}. of cou...

Questions in other subjects:

Konu
Mathematics, 18.07.2019 02:30