Dgdrxrt

Magento 2 - Add additional attributes in register

Flight departed from the gate 5 min before scheduled departure time. Refund options

What should one know about term logic before studying propositional and predicate logic?

Can a Knight grant Knighthood to another?

What did Turing mean when saying that "machines cannot give rise to surprises" is due to a fallacy?

How to name indistinguishable henchmen in a screenplay?

How do I say "this must not happen"?

Why can't fire hurt Daenerys but it did to Jon Snow in season 1?

Can stored/leased 737s be used to substitute for grounded MAXs?

Centre cell vertically in tabularx across multiple multiline rows

why doesn't university give past final exams' answers

How to make an animal which can only breed for a certain number of generations?

Weaponising the Grasp-at-a-Distance spell

Should man-made satellites feature an intelligent inverted "cow catcher"?

How to remove this numerical artifact?

Why not use the yoke to control yaw, as well as pitch and roll?

Plotting a Maclaurin series

Marquee sign letters

geoserver.catalog.FailedRequestError: Tried to make a GET request to http://localhost:8080/geoserver/workspaces.xml but got a 404 status code

How do you cope with tons of web fonts when copying and pasting from web pages?

Improvising over quartal voicings

Can I cut the hair of a conjured korred with a blade made of precious material to harvest that material from the korred?

malloc in main() or malloc in another function: allocating memory for a struct and its members

Inverse square law not accurate for non-point masses?

Turing Machine running itself?

0

$begingroup$

I am reading a proof that shows that the language $A_TM = M$ is a TM and $M$ accepts $w$ is undecidable. The proof proceeds by supposing there is a decider for the language $H,$ and a new TM $D$ that calls $H$ as a subroutine. $D$ runs by the following: On input $<M>,$ where $M$ is a TM, run $H$ on $<M, <M>>.$ Output the opposite of what H outputs...
I am confused by what $<M, <M>>$ means. Can somebody explain what it means for a machine to run on its own description?

computer-science computability

share|cite|improve this question

asked Oct 15 '16 at 23:41

伽罗瓦伽罗瓦

1,300615

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Use langle and rangle to get the angle-brackets for tuples. In comparison, < and > are comparison operators.
  $endgroup$
  – user21820
  Dec 29 '16 at 7:02
  

  
  
  
  

add a comment | 

0

$begingroup$

I am reading a proof that shows that the language $A_TM = M$ is a TM and $M$ accepts $w$ is undecidable. The proof proceeds by supposing there is a decider for the language $H,$ and a new TM $D$ that calls $H$ as a subroutine. $D$ runs by the following: On input $<M>,$ where $M$ is a TM, run $H$ on $<M, <M>>.$ Output the opposite of what H outputs...
I am confused by what $<M, <M>>$ means. Can somebody explain what it means for a machine to run on its own description?

computer-science computability

share|cite|improve this question

asked Oct 15 '16 at 23:41

伽罗瓦伽罗瓦

1,300615

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Use langle and rangle to get the angle-brackets for tuples. In comparison, < and > are comparison operators.
  $endgroup$
  – user21820
  Dec 29 '16 at 7:02
  

  
  
  
  

add a comment | 

$begingroup$

I am reading a proof that shows that the language $A_TM = M$ is a TM and $M$ accepts $w$ is undecidable. The proof proceeds by supposing there is a decider for the language $H,$ and a new TM $D$ that calls $H$ as a subroutine. $D$ runs by the following: On input $<M>,$ where $M$ is a TM, run $H$ on $<M, <M>>.$ Output the opposite of what H outputs...
I am confused by what $<M, <M>>$ means. Can somebody explain what it means for a machine to run on its own description?

computer-science computability

share|cite|improve this question

asked Oct 15 '16 at 23:41

伽罗瓦伽罗瓦

1,300615

$endgroup$

share|cite|improve this question

asked Oct 15 '16 at 23:41

伽罗瓦伽罗瓦

1,300615

share|cite|improve this question

asked Oct 15 '16 at 23:41

伽罗瓦伽罗瓦

1,300615

asked Oct 15 '16 at 23:41

伽罗瓦伽罗瓦

1,300615

asked Oct 15 '16 at 23:41

伽罗瓦伽罗瓦

1,300615

1 Answer
1

active

oldest

votes

0

$begingroup$

From your question I assume that you use a definition of Turing machines which are defined on strings as input.
If $M$ is the description of a Turing machine, then $<M>$ would be the description as a string, so you can actually use it as input. The technique of running a Turing machine with its own code as input is widely known as "diagonalization", a proof technique widely used in computability theory.

By clever coding you can build a one-one correspondence between finite strings and descriptions of Turing machine. I am sure that this is explained in the text you are reading, for instance when Universal Turing machines are introduced.

In the notation widely accepted in the computability theoretic community where $phi_x$ is the Turing machine with code $x$ and assuming that your machine $D$ has code $d$, it would read as
$$phi_d(x)=begincases 1 & phi_x(x)=0\
0& phi_x(x)=1
endcases$$

share|cite|improve this answer

edited Oct 16 '16 at 11:35

answered Oct 16 '16 at 10:40

Dino RosseggerDino Rossegger

608

$endgroup$

add a comment | 

Your Answer

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1970253%2fturing-machine-running-itself%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

0

$begingroup$

From your question I assume that you use a definition of Turing machines which are defined on strings as input.
If $M$ is the description of a Turing machine, then $<M>$ would be the description as a string, so you can actually use it as input. The technique of running a Turing machine with its own code as input is widely known as "diagonalization", a proof technique widely used in computability theory.

By clever coding you can build a one-one correspondence between finite strings and descriptions of Turing machine. I am sure that this is explained in the text you are reading, for instance when Universal Turing machines are introduced.

In the notation widely accepted in the computability theoretic community where $phi_x$ is the Turing machine with code $x$ and assuming that your machine $D$ has code $d$, it would read as
$$phi_d(x)=begincases 1 & phi_x(x)=0\
0& phi_x(x)=1
endcases$$

share|cite|improve this answer

edited Oct 16 '16 at 11:35

answered Oct 16 '16 at 10:40

Dino RosseggerDino Rossegger

608

$endgroup$

add a comment | 

0

$begingroup$

From your question I assume that you use a definition of Turing machines which are defined on strings as input.
If $M$ is the description of a Turing machine, then $<M>$ would be the description as a string, so you can actually use it as input. The technique of running a Turing machine with its own code as input is widely known as "diagonalization", a proof technique widely used in computability theory.

By clever coding you can build a one-one correspondence between finite strings and descriptions of Turing machine. I am sure that this is explained in the text you are reading, for instance when Universal Turing machines are introduced.

In the notation widely accepted in the computability theoretic community where $phi_x$ is the Turing machine with code $x$ and assuming that your machine $D$ has code $d$, it would read as
$$phi_d(x)=begincases 1 & phi_x(x)=0\
0& phi_x(x)=1
endcases$$

share|cite|improve this answer

edited Oct 16 '16 at 11:35

answered Oct 16 '16 at 10:40

Dino RosseggerDino Rossegger

608

$endgroup$

add a comment | 

$begingroup$

From your question I assume that you use a definition of Turing machines which are defined on strings as input.
If $M$ is the description of a Turing machine, then $<M>$ would be the description as a string, so you can actually use it as input. The technique of running a Turing machine with its own code as input is widely known as "diagonalization", a proof technique widely used in computability theory.

By clever coding you can build a one-one correspondence between finite strings and descriptions of Turing machine. I am sure that this is explained in the text you are reading, for instance when Universal Turing machines are introduced.

In the notation widely accepted in the computability theoretic community where $phi_x$ is the Turing machine with code $x$ and assuming that your machine $D$ has code $d$, it would read as
$$phi_d(x)=begincases 1 & phi_x(x)=0\
0& phi_x(x)=1
endcases$$

share|cite|improve this answer

edited Oct 16 '16 at 11:35

answered Oct 16 '16 at 10:40

Dino RosseggerDino Rossegger

608

$endgroup$

share|cite|improve this answer

edited Oct 16 '16 at 11:35

answered Oct 16 '16 at 10:40

Dino RosseggerDino Rossegger

608

answered Oct 16 '16 at 10:40

Dino RosseggerDino Rossegger

608

answered Oct 16 '16 at 10:40

Dino RosseggerDino Rossegger

608