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, hadellolo8839
Acompressor receives the shaft work to decrease the pressure of the fluid. a)- true b)- false
Answers: 3
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, lillygrl100
For the closed feedwater heater below, feedwater enters state 3 at a pressure of 2000 psia and temperature of 420 °f at a rate of ix10 ibhr. the feedwat extracted steam enters state 1 at a pressure of 1000 psia and enthalpy of 1500 btu/lbm. the extracted er leaves at an enthalpy of 528.7 btu/lbm steam leaves as a saturated liquid. (16) a) determine the mass flow rate of the extraction steam used to heat the feedwater (10) b) determine the terminal temperature difference of the closed feedwater heater
Answers: 3
image
Engineering, 04.07.2019 18:10, jojoangelique13
The flow rate of air through a through a pipe is 0.02 m5/s. a pitot static tube is placed in the flow. the radius of the pitot static tube is 1 mm. assuming the flow to be steady and the air to be at 300k, calculate the difference in total and static pressure if the diameter of the pipe is: (a) d 0.1 m d 0.05 m (c) d 0.01 m
Answers: 2
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: