Some basic questions on halt and move in Turing machines












2












$begingroup$


Im trying to learn about and set up Turing Machines (TMs) the simplest ways using the simplest definite rules. I am using my previous knowledge on simple Cellular Automata to do this. I want to write the computer code, but first I have to get some understanding of the restrictions and possibilities of TMs.



Firstly i define an operation as follows:



Operation (Op)



Do operation based on current color ($C$) and its state ($S$) i.e. $Op(c, s)$:




  1. replace color $C$ with $0$ or $1$. (at current position of tape head) move

  2. tape-head (change its position).

  3. change state $S$ with $0$ or $1$ (at new position).


For each operation:




  • In general does a TM only have only one halting-operation?
    (i.e. can only one operation promote the halting or can more than one operation do that?).


  • Can the tape-head also stop at a fixed position? (i.e. not move its head).
    Instead of the rules $0$ (move left) and $1$ (move right), it can also $2$ (not move anywhere) or even jump two units to the left or right?



My last question is basically the same as the last question..




  • Can the tape-head move more than one unit to the left or right?


The reason I ask this, is because if there is only one halting state in no more than one operation, the number of rules (in my setup) can be reduced. And if the tape-head can move more than one unit either to the left or right or both my guess is that it can produce more complex outputs. But my questions are concerning what is the limitations of a Turing Machine.



Example



If something was unclear I can try this example:



  inp:    outp:
Op(0,0) => 110
Op(0,1) => 101
Op(1,0) => 111
Op(1,1) => 001*


Of the output ($b_2b_1b_0$), where the first bit ($b_0$) represent the tapehead-move direction, $b_1$ represents the new state, and $b_0$ represents the changed color.
The asterisk shows that a halting operation should be performed.



The first question I asked wether there was possible to have more than one halting operation in a TM. Basically I ask wether I can have two or more asterisks like this, or if its not allowed:



  inp:    outp:
Op(0,0) => 110
Op(0,1) => 101
Op(1,0) => 111*
Op(1,1) => 001*


Recap



So can more than one operation perform the halting operation?



Can we move the tape head more than one unit to the left or right, or can it stand still?










share|cite|improve this question









$endgroup$












  • $begingroup$
    You can define your Turing machine model in whichever reasonable way you want, as long as the resulting model is equal in power to a standard Turing machine.
    $endgroup$
    – Yuval Filmus
    2 days ago






  • 1




    $begingroup$
    If you are interested in a specific model of Turing machines, then you'll have to specify your model, and then you'll likely be able to answer these questions on your own.
    $endgroup$
    – Yuval Filmus
    2 days ago










  • $begingroup$
    Thanks, but where can I find info on a standard Turing machine? Was my above descriptions close?
    $endgroup$
    – Natural Number Guy
    2 days ago






  • 3




    $begingroup$
    There is no single standard model of a Turing machine. You can find (similar but not identical) definitions on Wikipedia and in any number of textbooks.
    $endgroup$
    – Yuval Filmus
    2 days ago
















2












$begingroup$


Im trying to learn about and set up Turing Machines (TMs) the simplest ways using the simplest definite rules. I am using my previous knowledge on simple Cellular Automata to do this. I want to write the computer code, but first I have to get some understanding of the restrictions and possibilities of TMs.



Firstly i define an operation as follows:



Operation (Op)



Do operation based on current color ($C$) and its state ($S$) i.e. $Op(c, s)$:




  1. replace color $C$ with $0$ or $1$. (at current position of tape head) move

  2. tape-head (change its position).

  3. change state $S$ with $0$ or $1$ (at new position).


For each operation:




  • In general does a TM only have only one halting-operation?
    (i.e. can only one operation promote the halting or can more than one operation do that?).


  • Can the tape-head also stop at a fixed position? (i.e. not move its head).
    Instead of the rules $0$ (move left) and $1$ (move right), it can also $2$ (not move anywhere) or even jump two units to the left or right?



My last question is basically the same as the last question..




  • Can the tape-head move more than one unit to the left or right?


The reason I ask this, is because if there is only one halting state in no more than one operation, the number of rules (in my setup) can be reduced. And if the tape-head can move more than one unit either to the left or right or both my guess is that it can produce more complex outputs. But my questions are concerning what is the limitations of a Turing Machine.



Example



If something was unclear I can try this example:



  inp:    outp:
Op(0,0) => 110
Op(0,1) => 101
Op(1,0) => 111
Op(1,1) => 001*


Of the output ($b_2b_1b_0$), where the first bit ($b_0$) represent the tapehead-move direction, $b_1$ represents the new state, and $b_0$ represents the changed color.
The asterisk shows that a halting operation should be performed.



The first question I asked wether there was possible to have more than one halting operation in a TM. Basically I ask wether I can have two or more asterisks like this, or if its not allowed:



  inp:    outp:
Op(0,0) => 110
Op(0,1) => 101
Op(1,0) => 111*
Op(1,1) => 001*


Recap



So can more than one operation perform the halting operation?



Can we move the tape head more than one unit to the left or right, or can it stand still?










share|cite|improve this question









$endgroup$












  • $begingroup$
    You can define your Turing machine model in whichever reasonable way you want, as long as the resulting model is equal in power to a standard Turing machine.
    $endgroup$
    – Yuval Filmus
    2 days ago






  • 1




    $begingroup$
    If you are interested in a specific model of Turing machines, then you'll have to specify your model, and then you'll likely be able to answer these questions on your own.
    $endgroup$
    – Yuval Filmus
    2 days ago










  • $begingroup$
    Thanks, but where can I find info on a standard Turing machine? Was my above descriptions close?
    $endgroup$
    – Natural Number Guy
    2 days ago






  • 3




    $begingroup$
    There is no single standard model of a Turing machine. You can find (similar but not identical) definitions on Wikipedia and in any number of textbooks.
    $endgroup$
    – Yuval Filmus
    2 days ago














2












2








2





$begingroup$


Im trying to learn about and set up Turing Machines (TMs) the simplest ways using the simplest definite rules. I am using my previous knowledge on simple Cellular Automata to do this. I want to write the computer code, but first I have to get some understanding of the restrictions and possibilities of TMs.



Firstly i define an operation as follows:



Operation (Op)



Do operation based on current color ($C$) and its state ($S$) i.e. $Op(c, s)$:




  1. replace color $C$ with $0$ or $1$. (at current position of tape head) move

  2. tape-head (change its position).

  3. change state $S$ with $0$ or $1$ (at new position).


For each operation:




  • In general does a TM only have only one halting-operation?
    (i.e. can only one operation promote the halting or can more than one operation do that?).


  • Can the tape-head also stop at a fixed position? (i.e. not move its head).
    Instead of the rules $0$ (move left) and $1$ (move right), it can also $2$ (not move anywhere) or even jump two units to the left or right?



My last question is basically the same as the last question..




  • Can the tape-head move more than one unit to the left or right?


The reason I ask this, is because if there is only one halting state in no more than one operation, the number of rules (in my setup) can be reduced. And if the tape-head can move more than one unit either to the left or right or both my guess is that it can produce more complex outputs. But my questions are concerning what is the limitations of a Turing Machine.



Example



If something was unclear I can try this example:



  inp:    outp:
Op(0,0) => 110
Op(0,1) => 101
Op(1,0) => 111
Op(1,1) => 001*


Of the output ($b_2b_1b_0$), where the first bit ($b_0$) represent the tapehead-move direction, $b_1$ represents the new state, and $b_0$ represents the changed color.
The asterisk shows that a halting operation should be performed.



The first question I asked wether there was possible to have more than one halting operation in a TM. Basically I ask wether I can have two or more asterisks like this, or if its not allowed:



  inp:    outp:
Op(0,0) => 110
Op(0,1) => 101
Op(1,0) => 111*
Op(1,1) => 001*


Recap



So can more than one operation perform the halting operation?



Can we move the tape head more than one unit to the left or right, or can it stand still?










share|cite|improve this question









$endgroup$




Im trying to learn about and set up Turing Machines (TMs) the simplest ways using the simplest definite rules. I am using my previous knowledge on simple Cellular Automata to do this. I want to write the computer code, but first I have to get some understanding of the restrictions and possibilities of TMs.



Firstly i define an operation as follows:



Operation (Op)



Do operation based on current color ($C$) and its state ($S$) i.e. $Op(c, s)$:




  1. replace color $C$ with $0$ or $1$. (at current position of tape head) move

  2. tape-head (change its position).

  3. change state $S$ with $0$ or $1$ (at new position).


For each operation:




  • In general does a TM only have only one halting-operation?
    (i.e. can only one operation promote the halting or can more than one operation do that?).


  • Can the tape-head also stop at a fixed position? (i.e. not move its head).
    Instead of the rules $0$ (move left) and $1$ (move right), it can also $2$ (not move anywhere) or even jump two units to the left or right?



My last question is basically the same as the last question..




  • Can the tape-head move more than one unit to the left or right?


The reason I ask this, is because if there is only one halting state in no more than one operation, the number of rules (in my setup) can be reduced. And if the tape-head can move more than one unit either to the left or right or both my guess is that it can produce more complex outputs. But my questions are concerning what is the limitations of a Turing Machine.



Example



If something was unclear I can try this example:



  inp:    outp:
Op(0,0) => 110
Op(0,1) => 101
Op(1,0) => 111
Op(1,1) => 001*


Of the output ($b_2b_1b_0$), where the first bit ($b_0$) represent the tapehead-move direction, $b_1$ represents the new state, and $b_0$ represents the changed color.
The asterisk shows that a halting operation should be performed.



The first question I asked wether there was possible to have more than one halting operation in a TM. Basically I ask wether I can have two or more asterisks like this, or if its not allowed:



  inp:    outp:
Op(0,0) => 110
Op(0,1) => 101
Op(1,0) => 111*
Op(1,1) => 001*


Recap



So can more than one operation perform the halting operation?



Can we move the tape head more than one unit to the left or right, or can it stand still?







turing-machines automata






share|cite|improve this question













share|cite|improve this question











share|cite|improve this question




share|cite|improve this question










asked 2 days ago









Natural Number GuyNatural Number Guy

1154




1154












  • $begingroup$
    You can define your Turing machine model in whichever reasonable way you want, as long as the resulting model is equal in power to a standard Turing machine.
    $endgroup$
    – Yuval Filmus
    2 days ago






  • 1




    $begingroup$
    If you are interested in a specific model of Turing machines, then you'll have to specify your model, and then you'll likely be able to answer these questions on your own.
    $endgroup$
    – Yuval Filmus
    2 days ago










  • $begingroup$
    Thanks, but where can I find info on a standard Turing machine? Was my above descriptions close?
    $endgroup$
    – Natural Number Guy
    2 days ago






  • 3




    $begingroup$
    There is no single standard model of a Turing machine. You can find (similar but not identical) definitions on Wikipedia and in any number of textbooks.
    $endgroup$
    – Yuval Filmus
    2 days ago


















  • $begingroup$
    You can define your Turing machine model in whichever reasonable way you want, as long as the resulting model is equal in power to a standard Turing machine.
    $endgroup$
    – Yuval Filmus
    2 days ago






  • 1




    $begingroup$
    If you are interested in a specific model of Turing machines, then you'll have to specify your model, and then you'll likely be able to answer these questions on your own.
    $endgroup$
    – Yuval Filmus
    2 days ago










  • $begingroup$
    Thanks, but where can I find info on a standard Turing machine? Was my above descriptions close?
    $endgroup$
    – Natural Number Guy
    2 days ago






  • 3




    $begingroup$
    There is no single standard model of a Turing machine. You can find (similar but not identical) definitions on Wikipedia and in any number of textbooks.
    $endgroup$
    – Yuval Filmus
    2 days ago
















$begingroup$
You can define your Turing machine model in whichever reasonable way you want, as long as the resulting model is equal in power to a standard Turing machine.
$endgroup$
– Yuval Filmus
2 days ago




$begingroup$
You can define your Turing machine model in whichever reasonable way you want, as long as the resulting model is equal in power to a standard Turing machine.
$endgroup$
– Yuval Filmus
2 days ago




1




1




$begingroup$
If you are interested in a specific model of Turing machines, then you'll have to specify your model, and then you'll likely be able to answer these questions on your own.
$endgroup$
– Yuval Filmus
2 days ago




$begingroup$
If you are interested in a specific model of Turing machines, then you'll have to specify your model, and then you'll likely be able to answer these questions on your own.
$endgroup$
– Yuval Filmus
2 days ago












$begingroup$
Thanks, but where can I find info on a standard Turing machine? Was my above descriptions close?
$endgroup$
– Natural Number Guy
2 days ago




$begingroup$
Thanks, but where can I find info on a standard Turing machine? Was my above descriptions close?
$endgroup$
– Natural Number Guy
2 days ago




3




3




$begingroup$
There is no single standard model of a Turing machine. You can find (similar but not identical) definitions on Wikipedia and in any number of textbooks.
$endgroup$
– Yuval Filmus
2 days ago




$begingroup$
There is no single standard model of a Turing machine. You can find (similar but not identical) definitions on Wikipedia and in any number of textbooks.
$endgroup$
– Yuval Filmus
2 days ago










1 Answer
1






active

oldest

votes


















8












$begingroup$

To answer any kind of question like this, you need to choose one of the standard definitions of Turing machines (there are several but they're all essentially the same) and prove that adding the feature you want doesn't increase the computational power. You do that by showing how to simulate the feature using the standard machine.





  • In general does a TM only have only one halting-operation? (i.e. can only one operation promote the halting or can more than one operation do that?).




It doesn't matter. If you want three halting states and I insist that there can be only one, then have three states called $h_1$, $h_2$ and $h_3$ and design the transition function so that, if the machine ever enters one of those, its next transition is to $mathrm{HALT}$.





  • Can the tape-head also stop at a fixed position? (i.e. not move its head). Instead of the rules 0 (move left) and 1 (move right), it can also 2 (not move anywhere) or even jump two units to the left or right?




Again, it doesn't matter. If I insist you must move left or right, you can move one step left and then move back to the right; you can move two steps to the right by moving one step, twice.





  • Can the tape-head move more than one unit to the left or right?




Even that doesn't affect things: random-access Turing machines have an "address tape" onto which you can write a number and a special state that causes the head to move straight to the tape cell indexed by that number. Again, same power.



Multiple tapes, inserting and deleting characters, two-dimensional (or more!) tapes. Almost anything you can imagine makes no difference, and proving these things are standard exercises in computation theory textbooks.






share|cite|improve this answer









$endgroup$













  • $begingroup$
    One more question: What about the Buzzy Beaver TM, does the same rules apply there? Or do they have restricted rules on the movements and halting ops.
    $endgroup$
    – Natural Number Guy
    2 days ago










  • $begingroup$
    You can ask the busy beaver question for any specific definition of Turing machines. It probably doesn't make a lot of difference to the answer -- it's uncomputable regardless, and the answer to any busy beaver question is "some huge number".
    $endgroup$
    – David Richerby
    2 days ago












Your Answer





StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");

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


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f106651%2fsome-basic-questions-on-halt-and-move-in-turing-machines%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown

























1 Answer
1






active

oldest

votes








1 Answer
1






active

oldest

votes









active

oldest

votes






active

oldest

votes









8












$begingroup$

To answer any kind of question like this, you need to choose one of the standard definitions of Turing machines (there are several but they're all essentially the same) and prove that adding the feature you want doesn't increase the computational power. You do that by showing how to simulate the feature using the standard machine.





  • In general does a TM only have only one halting-operation? (i.e. can only one operation promote the halting or can more than one operation do that?).




It doesn't matter. If you want three halting states and I insist that there can be only one, then have three states called $h_1$, $h_2$ and $h_3$ and design the transition function so that, if the machine ever enters one of those, its next transition is to $mathrm{HALT}$.





  • Can the tape-head also stop at a fixed position? (i.e. not move its head). Instead of the rules 0 (move left) and 1 (move right), it can also 2 (not move anywhere) or even jump two units to the left or right?




Again, it doesn't matter. If I insist you must move left or right, you can move one step left and then move back to the right; you can move two steps to the right by moving one step, twice.





  • Can the tape-head move more than one unit to the left or right?




Even that doesn't affect things: random-access Turing machines have an "address tape" onto which you can write a number and a special state that causes the head to move straight to the tape cell indexed by that number. Again, same power.



Multiple tapes, inserting and deleting characters, two-dimensional (or more!) tapes. Almost anything you can imagine makes no difference, and proving these things are standard exercises in computation theory textbooks.






share|cite|improve this answer









$endgroup$













  • $begingroup$
    One more question: What about the Buzzy Beaver TM, does the same rules apply there? Or do they have restricted rules on the movements and halting ops.
    $endgroup$
    – Natural Number Guy
    2 days ago










  • $begingroup$
    You can ask the busy beaver question for any specific definition of Turing machines. It probably doesn't make a lot of difference to the answer -- it's uncomputable regardless, and the answer to any busy beaver question is "some huge number".
    $endgroup$
    – David Richerby
    2 days ago
















8












$begingroup$

To answer any kind of question like this, you need to choose one of the standard definitions of Turing machines (there are several but they're all essentially the same) and prove that adding the feature you want doesn't increase the computational power. You do that by showing how to simulate the feature using the standard machine.





  • In general does a TM only have only one halting-operation? (i.e. can only one operation promote the halting or can more than one operation do that?).




It doesn't matter. If you want three halting states and I insist that there can be only one, then have three states called $h_1$, $h_2$ and $h_3$ and design the transition function so that, if the machine ever enters one of those, its next transition is to $mathrm{HALT}$.





  • Can the tape-head also stop at a fixed position? (i.e. not move its head). Instead of the rules 0 (move left) and 1 (move right), it can also 2 (not move anywhere) or even jump two units to the left or right?




Again, it doesn't matter. If I insist you must move left or right, you can move one step left and then move back to the right; you can move two steps to the right by moving one step, twice.





  • Can the tape-head move more than one unit to the left or right?




Even that doesn't affect things: random-access Turing machines have an "address tape" onto which you can write a number and a special state that causes the head to move straight to the tape cell indexed by that number. Again, same power.



Multiple tapes, inserting and deleting characters, two-dimensional (or more!) tapes. Almost anything you can imagine makes no difference, and proving these things are standard exercises in computation theory textbooks.






share|cite|improve this answer









$endgroup$













  • $begingroup$
    One more question: What about the Buzzy Beaver TM, does the same rules apply there? Or do they have restricted rules on the movements and halting ops.
    $endgroup$
    – Natural Number Guy
    2 days ago










  • $begingroup$
    You can ask the busy beaver question for any specific definition of Turing machines. It probably doesn't make a lot of difference to the answer -- it's uncomputable regardless, and the answer to any busy beaver question is "some huge number".
    $endgroup$
    – David Richerby
    2 days ago














8












8








8





$begingroup$

To answer any kind of question like this, you need to choose one of the standard definitions of Turing machines (there are several but they're all essentially the same) and prove that adding the feature you want doesn't increase the computational power. You do that by showing how to simulate the feature using the standard machine.





  • In general does a TM only have only one halting-operation? (i.e. can only one operation promote the halting or can more than one operation do that?).




It doesn't matter. If you want three halting states and I insist that there can be only one, then have three states called $h_1$, $h_2$ and $h_3$ and design the transition function so that, if the machine ever enters one of those, its next transition is to $mathrm{HALT}$.





  • Can the tape-head also stop at a fixed position? (i.e. not move its head). Instead of the rules 0 (move left) and 1 (move right), it can also 2 (not move anywhere) or even jump two units to the left or right?




Again, it doesn't matter. If I insist you must move left or right, you can move one step left and then move back to the right; you can move two steps to the right by moving one step, twice.





  • Can the tape-head move more than one unit to the left or right?




Even that doesn't affect things: random-access Turing machines have an "address tape" onto which you can write a number and a special state that causes the head to move straight to the tape cell indexed by that number. Again, same power.



Multiple tapes, inserting and deleting characters, two-dimensional (or more!) tapes. Almost anything you can imagine makes no difference, and proving these things are standard exercises in computation theory textbooks.






share|cite|improve this answer









$endgroup$



To answer any kind of question like this, you need to choose one of the standard definitions of Turing machines (there are several but they're all essentially the same) and prove that adding the feature you want doesn't increase the computational power. You do that by showing how to simulate the feature using the standard machine.





  • In general does a TM only have only one halting-operation? (i.e. can only one operation promote the halting or can more than one operation do that?).




It doesn't matter. If you want three halting states and I insist that there can be only one, then have three states called $h_1$, $h_2$ and $h_3$ and design the transition function so that, if the machine ever enters one of those, its next transition is to $mathrm{HALT}$.





  • Can the tape-head also stop at a fixed position? (i.e. not move its head). Instead of the rules 0 (move left) and 1 (move right), it can also 2 (not move anywhere) or even jump two units to the left or right?




Again, it doesn't matter. If I insist you must move left or right, you can move one step left and then move back to the right; you can move two steps to the right by moving one step, twice.





  • Can the tape-head move more than one unit to the left or right?




Even that doesn't affect things: random-access Turing machines have an "address tape" onto which you can write a number and a special state that causes the head to move straight to the tape cell indexed by that number. Again, same power.



Multiple tapes, inserting and deleting characters, two-dimensional (or more!) tapes. Almost anything you can imagine makes no difference, and proving these things are standard exercises in computation theory textbooks.







share|cite|improve this answer












share|cite|improve this answer



share|cite|improve this answer










answered 2 days ago









David RicherbyDavid Richerby

70k15106196




70k15106196












  • $begingroup$
    One more question: What about the Buzzy Beaver TM, does the same rules apply there? Or do they have restricted rules on the movements and halting ops.
    $endgroup$
    – Natural Number Guy
    2 days ago










  • $begingroup$
    You can ask the busy beaver question for any specific definition of Turing machines. It probably doesn't make a lot of difference to the answer -- it's uncomputable regardless, and the answer to any busy beaver question is "some huge number".
    $endgroup$
    – David Richerby
    2 days ago


















  • $begingroup$
    One more question: What about the Buzzy Beaver TM, does the same rules apply there? Or do they have restricted rules on the movements and halting ops.
    $endgroup$
    – Natural Number Guy
    2 days ago










  • $begingroup$
    You can ask the busy beaver question for any specific definition of Turing machines. It probably doesn't make a lot of difference to the answer -- it's uncomputable regardless, and the answer to any busy beaver question is "some huge number".
    $endgroup$
    – David Richerby
    2 days ago
















$begingroup$
One more question: What about the Buzzy Beaver TM, does the same rules apply there? Or do they have restricted rules on the movements and halting ops.
$endgroup$
– Natural Number Guy
2 days ago




$begingroup$
One more question: What about the Buzzy Beaver TM, does the same rules apply there? Or do they have restricted rules on the movements and halting ops.
$endgroup$
– Natural Number Guy
2 days ago












$begingroup$
You can ask the busy beaver question for any specific definition of Turing machines. It probably doesn't make a lot of difference to the answer -- it's uncomputable regardless, and the answer to any busy beaver question is "some huge number".
$endgroup$
– David Richerby
2 days ago




$begingroup$
You can ask the busy beaver question for any specific definition of Turing machines. It probably doesn't make a lot of difference to the answer -- it's uncomputable regardless, and the answer to any busy beaver question is "some huge number".
$endgroup$
– David Richerby
2 days ago


















draft saved

draft discarded




















































Thanks for contributing an answer to Computer Science Stack Exchange!


  • Please be sure to answer the question. Provide details and share your research!

But avoid



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


Use MathJax to format equations. MathJax reference.


To learn more, see our tips on writing great answers.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f106651%2fsome-basic-questions-on-halt-and-move-in-turing-machines%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown





















































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown

































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown







Popular posts from this blog

GameSpot

日野市

Tu-95轟炸機