Some basic questions on halt and move in Turing machines“Print 'em all game” for Turing machinesPower of variants of Turing machinesThe control in the Turing MachineThe halting problem of Turing machines in view of enumeration of initial tape configurationsDifficulty in the halting problem for a simple Turing machine with standard enumerations of programs and of initial tape configurationsTuring machine that computes w#w when the input is w?Construct a Turing Machine that recognizes the set $0^2n1^n$For multi-tape Turing machines, can we assume that each tape can be in its own state independently of the other tapes?How would you create a Turing machine that copies a string and prints it to the tape?Turing machine - Transition between two states by more than one condition allowed?

Is every set a filtered colimit of finite sets?

How would photo IDs work for shapeshifters?

How to manage monthly salary

Is Social Media Science Fiction?

Extreme, but not acceptable situation and I can't start the work tomorrow morning

What do you call something that goes against the spirit of the law, but is legal when interpreting the law to the letter?

What is the meaning of "of trouble" in the following sentence?

Symmetry in quantum mechanics

Can I find out the caloric content of bread by dehydrating it?

What is the offset in a seaplane's hull?

Lied on resume at previous job

When blogging recipes, how can I support both readers who want the narrative/journey and ones who want the printer-friendly recipe?

"listening to me about as much as you're listening to this pole here"

What is GPS' 19 year rollover and does it present a cybersecurity issue?

How could a lack of term limits lead to a "dictatorship?"

Does the average primeness of natural numbers tend to zero?

Is this relativistic mass?

Can the Produce Flame cantrip be used to grapple, or as an unarmed strike, in the right circumstances?

Information to fellow intern about hiring?

Domain expired, GoDaddy holds it and is asking more money

Are white and non-white police officers equally likely to kill black suspects?

Why is the design of haulage companies so “special”?

How to make payment on the internet without leaving a money trail?

Is ipsum/ipsa/ipse a third person pronoun, or can it serve other functions?



Some basic questions on halt and move in Turing machines


“Print 'em all game” for Turing machinesPower of variants of Turing machinesThe control in the Turing MachineThe halting problem of Turing machines in view of enumeration of initial tape configurationsDifficulty in the halting problem for a simple Turing machine with standard enumerations of programs and of initial tape configurationsTuring machine that computes w#w when the input is w?Construct a Turing Machine that recognizes the set $ngeq 0$For multi-tape Turing machines, can we assume that each tape can be in its own state independently of the other tapes?How would you create a Turing machine that copies a string and prints it to the tape?Turing machine - Transition between two states by more than one condition allowed?













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
    16 hours 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
    16 hours ago










  • $begingroup$
    Thanks, but where can I find info on a standard Turing machine? Was my above descriptions close?
    $endgroup$
    – Natural Number Guy
    15 hours 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
    15 hours 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
    16 hours 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
    16 hours ago










  • $begingroup$
    Thanks, but where can I find info on a standard Turing machine? Was my above descriptions close?
    $endgroup$
    – Natural Number Guy
    15 hours 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
    15 hours 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 16 hours 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
    16 hours 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
    16 hours ago










  • $begingroup$
    Thanks, but where can I find info on a standard Turing machine? Was my above descriptions close?
    $endgroup$
    – Natural Number Guy
    15 hours 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
    15 hours 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
    16 hours 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
    16 hours ago










  • $begingroup$
    Thanks, but where can I find info on a standard Turing machine? Was my above descriptions close?
    $endgroup$
    – Natural Number Guy
    15 hours 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
    15 hours 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
16 hours 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
16 hours 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
16 hours 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
16 hours ago












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




$begingroup$
Thanks, but where can I find info on a standard Turing machine? Was my above descriptions close?
$endgroup$
– Natural Number Guy
15 hours 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
15 hours 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
15 hours 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 $mathrmHALT$.




  • 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
    7 hours 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
    7 hours 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 $mathrmHALT$.




  • 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
    7 hours 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
    7 hours 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 $mathrmHALT$.




  • 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
    7 hours 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
    7 hours 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 $mathrmHALT$.




  • 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 $mathrmHALT$.




  • 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 14 hours ago









David RicherbyDavid Richerby

69.8k15106195




69.8k15106195











  • $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
    7 hours 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
    7 hours 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
    7 hours 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
    7 hours 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
7 hours 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
7 hours 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
7 hours 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
7 hours 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

Disable / Remove link to Product Items in Cart Planned maintenance scheduled April 23, 2019 at 23:30 UTC (7:30pm US/Eastern) Announcing the arrival of Valued Associate #679: Cesar Manara Unicorn Meta Zoo #1: Why another podcast?How can I limit products that can be bought / added to cart?Remove item from cartHide “Add to Cart” button if specific products are already in cart“Prettifying” the custom options in cart pageCreate link in cart sidebar to view all added items After limit reachedLink products together in checkout/cartHow to Get product from cart and add it againHide action-edit on cart page if simple productRemoving Cart items - ObserverRemove wishlist items when added to cart

Helsingin valtaus Sisällysluettelo Taustaa | Yleistä sotatoimista | Osapuolet | Taistelut Helsingin ympäristössä | Punaisten antautumissuunnitelma | Taistelujen kulku Helsingissä | Valtauksen jälkeen | Tappiot | Muistaminen | Kirjallisuutta | Lähteet | Aiheesta muualla | NavigointivalikkoTeoksen verkkoversioTeoksen verkkoversioGoogle BooksSisällissota Helsingissä päättyi tasan 95 vuotta sittenSaksalaisten ylivoima jyräsi punaisen HelsinginSuomalaiset kuvaavat sotien jälkiä kaupungeissa – katso kuvat ja tarinat tutuilta kulmiltaHelsingin valtaus 90 vuotta sittenSaksalaiset valtasivat HelsinginHyökkäys HelsinkiinHelsingin valtaus 12.–13.4. 1918Saksalaiset käyttivät ihmiskilpiä Helsingin valtauksessa 1918Teoksen verkkoversioTeoksen verkkoversioSaksalaiset hyökkäävät Etelä-SuomeenTaistelut LeppävaarassaSotilaat ja taistelutLeppävaara 1918 huhtikuussa. KapinatarinaHelsingin taistelut 1918Saksalaisten voitonparaati HelsingissäHelsingin valtausta juhlittiinSaksalaisten Helsinki vuonna 1918Helsingin taistelussa kaatuneet valkokaartilaisetHelsinkiin haudatut taisteluissa kaatuneet punaiset12.4.1918 Helsingin valtauksessa saksalaiset apujoukot vapauttavat kaupunginVapaussodan muistomerkkejä Helsingissä ja pääkaupunkiseudullaCrescendo / Vuoden 1918 Kansalaissodan uhrien muistomerkkim

Adjektiivitarina Tarinan tekeminen | Esimerkki: ennen | Esimerkki: jälkeen | Navigointivalikko