Mfcttrf

Is my background sufficient to start Quantum Computing

German idiomatic equivalents of 能骗就骗 (if you can cheat, then cheat)

Square wave to sawtooth wave using two BJT

Replacing 5 gang light switches that have 3 of them daisy chained together

Why are examinees often not allowed to leave during the start and end of an exam?

Searching for single buildings in QGIS

Could citing a database like libgen get one into trouble?

What prevents a US state from colonizing a smaller state?

What was the ASCII end of medium (EM) character intended to be used for?

My players like to search everything. What do they find?

How can solar sailed ships be protected from space debris?

Is it OK to say "The situation is pregnant with a crisis"?

Confusion in understanding the behavior of inductor in RL circuit with DC source

Is it advisable to inform the CEO about his brother accessing his office?

I agreed to cancel a long-planned vacation (with travel costs) due to project deadlines, but now the timeline has all changed again

Why can't i use !(single pattern) in zsh even after i turn on kshglob?

How to idiomatically express the idea "if you can cheat without being caught, do it"

Why should I allow multiple IP addresses on a website for a single session?

Is it OK to throw pebbles and stones in streams, waterfalls, ponds, etc.?

How far can gerrymandering go?

Making arrow with a gradual colour

Why are symbols not written in words?

Why is my 401k manager recommending me to save more?

What's the idiomatic (or best) way to trim surrounding whitespace from a string?

Turing Machines: What is the difference between recognizing, deciding, total, accepting, rejecting?

What is the difference between a TM accepting and deciding a language?What is the difference between a TM accepting and deciding a language?Turing DecidableProof by Reduction: From Empty Language to Halting Problem on Empty InputShowing a problem is decidableShow that 0^n1^n is decidableWhats the difference between an oracle and a decider in Computational Theory?Equivalence between different Turing Machines and a definition of simulationA language which is neither r.e. nor co-r.eProving language K is undecidable using the diagonalization methodQuestions about Turing Machine

2

$begingroup$

I have seen a remark saying "we usually say that a turing machine accepts/rejects a string, while it decides a language" Is this correct?

As I have also seen places where we mention a Turing machine "accepting a language"

See comment on OP's answer here, then the answer by Jan Hudec : What is the difference between a TM accepting and deciding a language?

I have also seen the definition of total/decider to mean, the Turing machine halts on all inputs. Is this all inputs in the language the Turing Machine is defined over?

turing-machines

share|cite|improve this question

asked 8 hours ago

WeCanBeFriendsWeCanBeFriends

22255 bronze badges

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  There's no such thing as "the language the Turing machine is defined over".
  $endgroup$
  – Yuval Filmus
  8 hours ago
  
  

  
  
  
  

add a comment | 

2

$begingroup$

I have seen a remark saying "we usually say that a turing machine accepts/rejects a string, while it decides a language" Is this correct?

As I have also seen places where we mention a Turing machine "accepting a language"

See comment on OP's answer here, then the answer by Jan Hudec : What is the difference between a TM accepting and deciding a language?

I have also seen the definition of total/decider to mean, the Turing machine halts on all inputs. Is this all inputs in the language the Turing Machine is defined over?

turing-machines

share|cite|improve this question

asked 8 hours ago

WeCanBeFriendsWeCanBeFriends

22255 bronze badges

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  There's no such thing as "the language the Turing machine is defined over".
  $endgroup$
  – Yuval Filmus
  8 hours ago
  
  

  
  
  
  

add a comment | 

$begingroup$

I have seen a remark saying "we usually say that a turing machine accepts/rejects a string, while it decides a language" Is this correct?

As I have also seen places where we mention a Turing machine "accepting a language"

See comment on OP's answer here, then the answer by Jan Hudec : What is the difference between a TM accepting and deciding a language?

I have also seen the definition of total/decider to mean, the Turing machine halts on all inputs. Is this all inputs in the language the Turing Machine is defined over?

turing-machines

share|cite|improve this question

asked 8 hours ago

WeCanBeFriendsWeCanBeFriends

22255 bronze badges

$endgroup$

share|cite|improve this question

asked 8 hours ago

WeCanBeFriendsWeCanBeFriends

22255 bronze badges

share|cite|improve this question

asked 8 hours ago

WeCanBeFriendsWeCanBeFriends

22255 bronze badges

asked 8 hours ago

WeCanBeFriendsWeCanBeFriends

22255 bronze badges

asked 8 hours ago

WeCanBeFriendsWeCanBeFriends

22255 bronze badges

2 Answers
2

active

oldest

votes

5

$begingroup$

A Turing machine cannot accept a language.

A Turing Machine will either accept or reject a string. We know it accepts the string because it will halt in an accepting state. It is said to reject a string, of it halts in a rejecting state.

A TM recognises a language, if it halts and accepts all strings in that language

A Turing machine decides a language if it halts and accepts on all strings in that language, and halts and rejects for any string not in that language.

A total Turing machine or a decider is a machine that always halts regardless of the input. If a TM decides a language, then it is decider by definition or a total Turing Machine.

Edit:

To answer some of the questions in the OPs comments:

• A language does not define a Turing Machine. The TM defines the language; this language is set of all inputs that the TM halts and accepts on.




• All finite languages are decidable which means that there is a corresponding Turing machine which is a decider

share|cite|improve this answer

answered 6 hours ago

user679128user679128

14122 bronze badges

$endgroup$

add a comment | 

2

$begingroup$

One considers two different types of Turing machines:

• Total Turing machines: these are machines that are guaranteed to halt on all inputs. Sometimes known as deciders. If they halt in an accepting state, then the input is accepted; otherwise it is rejected. When interested in this kind of machine, we generally define the language accepted by the machine as the set of all inputs accepted by it.


• General Turing machines: these are machines that are not guaranteed to halt on all inputs (but may). When we are interested in this kind of machine, we generally associate with them the language of all inputs on which the machine halts.

share|cite|improve this answer

answered 8 hours ago

Yuval FilmusYuval Filmus

203k1515 gold badges197197 silver badges360360 bronze badges

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  How do I know a Turing machine is total? Maybe if the language defined by the Turing machine is finite?
  $endgroup$
  – WeCanBeFriends
  7 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  A Turing machine is total if it halts on all inputs. This is the definition.
  $endgroup$
  – Yuval Filmus
  7 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Is it correct to say that a TM accepts a string? If so, does that mean it halts+accepts or does it mean it does not reject, ie it can loop?
  $endgroup$
  – WeCanBeFriends
  7 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Got it, but was wondering due to the halting problem, how do I know if it halts on all inputs? if the language is infinite
  $endgroup$
  – WeCanBeFriends
  7 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  A Turing machine accepts a string if it halts in an accepting state. That's the definition.
  $endgroup$
  – Yuval Filmus
  7 hours ago
  
  

  
  
  
  

 | 
show 3 more comments

Your Answer

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "419"
;
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: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
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
,
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%2fcs.stackexchange.com%2fquestions%2f111331%2fturing-machines-what-is-the-difference-between-recognizing-deciding-total-ac%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

5

$begingroup$

A Turing machine cannot accept a language.

A Turing Machine will either accept or reject a string. We know it accepts the string because it will halt in an accepting state. It is said to reject a string, of it halts in a rejecting state.

A TM recognises a language, if it halts and accepts all strings in that language

A Turing machine decides a language if it halts and accepts on all strings in that language, and halts and rejects for any string not in that language.

A total Turing machine or a decider is a machine that always halts regardless of the input. If a TM decides a language, then it is decider by definition or a total Turing Machine.

Edit:

To answer some of the questions in the OPs comments:

• A language does not define a Turing Machine. The TM defines the language; this language is set of all inputs that the TM halts and accepts on.




• All finite languages are decidable which means that there is a corresponding Turing machine which is a decider

share|cite|improve this answer

answered 6 hours ago

user679128user679128

14122 bronze badges

$endgroup$

add a comment | 

5

$begingroup$

A Turing machine cannot accept a language.

A Turing Machine will either accept or reject a string. We know it accepts the string because it will halt in an accepting state. It is said to reject a string, of it halts in a rejecting state.

A TM recognises a language, if it halts and accepts all strings in that language

A Turing machine decides a language if it halts and accepts on all strings in that language, and halts and rejects for any string not in that language.

A total Turing machine or a decider is a machine that always halts regardless of the input. If a TM decides a language, then it is decider by definition or a total Turing Machine.

Edit:

To answer some of the questions in the OPs comments:

• A language does not define a Turing Machine. The TM defines the language; this language is set of all inputs that the TM halts and accepts on.




• All finite languages are decidable which means that there is a corresponding Turing machine which is a decider

share|cite|improve this answer

answered 6 hours ago

user679128user679128

14122 bronze badges

$endgroup$

add a comment | 

$begingroup$

A Turing machine cannot accept a language.

A Turing Machine will either accept or reject a string. We know it accepts the string because it will halt in an accepting state. It is said to reject a string, of it halts in a rejecting state.

A TM recognises a language, if it halts and accepts all strings in that language

A Turing machine decides a language if it halts and accepts on all strings in that language, and halts and rejects for any string not in that language.

A total Turing machine or a decider is a machine that always halts regardless of the input. If a TM decides a language, then it is decider by definition or a total Turing Machine.

Edit:

To answer some of the questions in the OPs comments:

• A language does not define a Turing Machine. The TM defines the language; this language is set of all inputs that the TM halts and accepts on.




• All finite languages are decidable which means that there is a corresponding Turing machine which is a decider

share|cite|improve this answer

answered 6 hours ago

user679128user679128

14122 bronze badges

$endgroup$

share|cite|improve this answer

answered 6 hours ago

user679128user679128

14122 bronze badges

answered 6 hours ago

user679128user679128

14122 bronze badges

answered 6 hours ago

user679128user679128

14122 bronze badges

2

$begingroup$

One considers two different types of Turing machines:

• Total Turing machines: these are machines that are guaranteed to halt on all inputs. Sometimes known as deciders. If they halt in an accepting state, then the input is accepted; otherwise it is rejected. When interested in this kind of machine, we generally define the language accepted by the machine as the set of all inputs accepted by it.


• General Turing machines: these are machines that are not guaranteed to halt on all inputs (but may). When we are interested in this kind of machine, we generally associate with them the language of all inputs on which the machine halts.

share|cite|improve this answer

answered 8 hours ago

Yuval FilmusYuval Filmus

203k1515 gold badges197197 silver badges360360 bronze badges

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  How do I know a Turing machine is total? Maybe if the language defined by the Turing machine is finite?
  $endgroup$
  – WeCanBeFriends
  7 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  A Turing machine is total if it halts on all inputs. This is the definition.
  $endgroup$
  – Yuval Filmus
  7 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Is it correct to say that a TM accepts a string? If so, does that mean it halts+accepts or does it mean it does not reject, ie it can loop?
  $endgroup$
  – WeCanBeFriends
  7 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Got it, but was wondering due to the halting problem, how do I know if it halts on all inputs? if the language is infinite
  $endgroup$
  – WeCanBeFriends
  7 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  A Turing machine accepts a string if it halts in an accepting state. That's the definition.
  $endgroup$
  – Yuval Filmus
  7 hours ago
  
  

  
  
  
  

 | 
show 3 more comments

2

$begingroup$

One considers two different types of Turing machines:

• Total Turing machines: these are machines that are guaranteed to halt on all inputs. Sometimes known as deciders. If they halt in an accepting state, then the input is accepted; otherwise it is rejected. When interested in this kind of machine, we generally define the language accepted by the machine as the set of all inputs accepted by it.


• General Turing machines: these are machines that are not guaranteed to halt on all inputs (but may). When we are interested in this kind of machine, we generally associate with them the language of all inputs on which the machine halts.

share|cite|improve this answer

answered 8 hours ago

Yuval FilmusYuval Filmus

203k1515 gold badges197197 silver badges360360 bronze badges

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  How do I know a Turing machine is total? Maybe if the language defined by the Turing machine is finite?
  $endgroup$
  – WeCanBeFriends
  7 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  A Turing machine is total if it halts on all inputs. This is the definition.
  $endgroup$
  – Yuval Filmus
  7 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Is it correct to say that a TM accepts a string? If so, does that mean it halts+accepts or does it mean it does not reject, ie it can loop?
  $endgroup$
  – WeCanBeFriends
  7 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Got it, but was wondering due to the halting problem, how do I know if it halts on all inputs? if the language is infinite
  $endgroup$
  – WeCanBeFriends
  7 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  A Turing machine accepts a string if it halts in an accepting state. That's the definition.
  $endgroup$
  – Yuval Filmus
  7 hours ago
  
  

  
  
  
  

 | 
show 3 more comments

$begingroup$

One considers two different types of Turing machines:

• Total Turing machines: these are machines that are guaranteed to halt on all inputs. Sometimes known as deciders. If they halt in an accepting state, then the input is accepted; otherwise it is rejected. When interested in this kind of machine, we generally define the language accepted by the machine as the set of all inputs accepted by it.


• General Turing machines: these are machines that are not guaranteed to halt on all inputs (but may). When we are interested in this kind of machine, we generally associate with them the language of all inputs on which the machine halts.

share|cite|improve this answer

answered 8 hours ago

Yuval FilmusYuval Filmus

203k1515 gold badges197197 silver badges360360 bronze badges

$endgroup$

share|cite|improve this answer

answered 8 hours ago

Yuval FilmusYuval Filmus

203k1515 gold badges197197 silver badges360360 bronze badges

answered 8 hours ago

Yuval FilmusYuval Filmus

203k1515 gold badges197197 silver badges360360 bronze badges

answered 8 hours ago

Yuval FilmusYuval Filmus

203k1515 gold badges197197 silver badges360360 bronze badges