Mdthbs

Pass USB 3.0 connection through D-SUB connector

What would be the effects of (relatively) widespread precognition on the stock market?

1025th term of the given sequence.

is FIND WORDS in P?

How to create quantum circuits from scratch

How did pilots avoid thunderstorms and related weather before “reliable” airborne weather radar was introduced on airliners?

Excluding specific string grep is also including similar strings

Cargo capacity of a kayak

Importance of moon phases for Apollo missions

Quickest way to move a line in a text file before another line in a text file?

Host telling me to cancel my booking in exchange for a discount?

Why didn't NASA launch communications relay satellites for the Apollo missions?

Is it better to have a 10 year gap or a bad reference?

Why is DC so, so, so Democratic?

What is the metal bit in the front of this propeller spinner?

How can electronics on board JWST survive the low operating temperature while it's difficult to survive lunar nights?

Count the identical pairs in two lists

My current job follows "worst practices". How can I talk about my experience in an interview without giving off red flags?

MITM on HTTPS traffic in Kazakhstan 2019

What does the following chess proverb mean: "Chess is a sea where a gnat may drink from and an elephant may bathe in."

Why is the UH-60 tail rotor canted?

What kind of vegetable has pink and white concentric rings?

What happens to a permanent I gained control over using Agent of Treachery, and I leave a multiplayer game?

Reset Column Header Index

Langton's Ant Periodic Behavior

Cellular Automata Using Small BoardsHow to synchronize a 2d cellular automaton in $Theta(sqrt{n} log n)$ stepsHow to prove universality in complex systems?What is the relation between pure mathematics, applied mathematics and Cellular Automata?What is the relation between universality and chaotic behavior in Elementary Cellular Automata?Why some rules in Elementary Cellular Automata halt and others don't?Consistent Simulation of Cellular Automata on Infinite GridSimple elementary cellular automata with high period?Classes of outer totalistic cellular automataDoes any algorithm exist for computing the state of a non-trivial cellular automaton after an arbitrary number of time steps?

.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ margin-bottom:0;
}

3

$begingroup$

I was wondering if there's any initial configuration which generates a pure periodic behavior for Langton's Ant?

cellular-automata

share|cite|improve this question

asked 10 hours ago

RameshRamesh

1833 bronze badges

New contributor

Ramesh is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

add a comment | 

3

$begingroup$

I was wondering if there's any initial configuration which generates a pure periodic behavior for Langton's Ant?

cellular-automata

share|cite|improve this question

asked 10 hours ago

RameshRamesh

1833 bronze badges

New contributor

Ramesh is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

add a comment | 

$begingroup$

I was wondering if there's any initial configuration which generates a pure periodic behavior for Langton's Ant?

cellular-automata

share|cite|improve this question

asked 10 hours ago

RameshRamesh

1833 bronze badges

New contributor

Ramesh is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

share|cite|improve this question

asked 10 hours ago

RameshRamesh

1833 bronze badges

New contributor

Ramesh is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

share|cite|improve this question

asked 10 hours ago

RameshRamesh

1833 bronze badges

New contributor

Ramesh is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

asked 10 hours ago

RameshRamesh

1833 bronze badges

New contributor

Ramesh is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

asked 10 hours ago

RameshRamesh

1833 bronze badges

1 Answer
1

active

oldest

votes

5

$begingroup$

The so-called Kohen–Kong theorem (described and attributed, without citation, to X.P. Kong and E.G.D. Kohen by Stewart (1994) (PDF); sometimes apparently misspelled as the "Kohen–Kung theorem") says that the path of Langton's ant can never be periodic (and, as a corollary, also cannot be bounded).

The proof is fairly simple, as the result follows directly from the following observations:

1. The path of the ant is (ultimately) periodic if and only if it is bounded. (Clearly, an unbounded path cannot be periodic. Conversely, if the ant would stay forever in a bounded region, there would be only a finite number of states in which the ant itself and the squares within that region could be, and therefore eventually the whole system would have to return to an earlier state.)


2. Since the ant turns 90° after every step, the direction from which it enters the next square alternates between horizontal and vertical. To return to a particular square after once leaving it, the ant must travel an even number of steps. Thus, if the ant once enters a given square horizontally (or vertically), it must always enter that square horizontally (or vertically).

Now, if the ant's path was periodic (and thus bounded), there would have to be a square that the ant visits repeatedly, but whose top and right neighbors the ant never visits during its periodic path. (To find such a square, just start from any square the ant is known to visit, and move up or right to adjacent visited squares as long as you can. Since the ant's path is, by assumption, bounded, this process will always terminate.) Thus, the ant must always either enter this square from the left and leave downwards, or enter it from below and leave left. But this means that the ant would have to always turn in the same direction after entering this square, which is impossible by definition.

share|cite|improve this answer

edited 5 hours ago

answered 9 hours ago

Ilmari KaronenIlmari Karonen

1,50188 silver badges1515 bronze badges

$endgroup$

add a comment | 

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
});


}
});

Ramesh is a new contributor. Be nice, and check out our Code of Conduct.

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%2f112075%2flangtons-ant-periodic-behavior%23new-answer', 'question_page');
}
);

Post as a guest

Name

Email

Required, but never shown

5

$begingroup$

The so-called Kohen–Kong theorem (described and attributed, without citation, to X.P. Kong and E.G.D. Kohen by Stewart (1994) (PDF); sometimes apparently misspelled as the "Kohen–Kung theorem") says that the path of Langton's ant can never be periodic (and, as a corollary, also cannot be bounded).

The proof is fairly simple, as the result follows directly from the following observations:

1. The path of the ant is (ultimately) periodic if and only if it is bounded. (Clearly, an unbounded path cannot be periodic. Conversely, if the ant would stay forever in a bounded region, there would be only a finite number of states in which the ant itself and the squares within that region could be, and therefore eventually the whole system would have to return to an earlier state.)


2. Since the ant turns 90° after every step, the direction from which it enters the next square alternates between horizontal and vertical. To return to a particular square after once leaving it, the ant must travel an even number of steps. Thus, if the ant once enters a given square horizontally (or vertically), it must always enter that square horizontally (or vertically).

Now, if the ant's path was periodic (and thus bounded), there would have to be a square that the ant visits repeatedly, but whose top and right neighbors the ant never visits during its periodic path. (To find such a square, just start from any square the ant is known to visit, and move up or right to adjacent visited squares as long as you can. Since the ant's path is, by assumption, bounded, this process will always terminate.) Thus, the ant must always either enter this square from the left and leave downwards, or enter it from below and leave left. But this means that the ant would have to always turn in the same direction after entering this square, which is impossible by definition.

share|cite|improve this answer

edited 5 hours ago

answered 9 hours ago

Ilmari KaronenIlmari Karonen

1,50188 silver badges1515 bronze badges

$endgroup$

add a comment | 

5

$begingroup$

The so-called Kohen–Kong theorem (described and attributed, without citation, to X.P. Kong and E.G.D. Kohen by Stewart (1994) (PDF); sometimes apparently misspelled as the "Kohen–Kung theorem") says that the path of Langton's ant can never be periodic (and, as a corollary, also cannot be bounded).

The proof is fairly simple, as the result follows directly from the following observations:

1. The path of the ant is (ultimately) periodic if and only if it is bounded. (Clearly, an unbounded path cannot be periodic. Conversely, if the ant would stay forever in a bounded region, there would be only a finite number of states in which the ant itself and the squares within that region could be, and therefore eventually the whole system would have to return to an earlier state.)


2. Since the ant turns 90° after every step, the direction from which it enters the next square alternates between horizontal and vertical. To return to a particular square after once leaving it, the ant must travel an even number of steps. Thus, if the ant once enters a given square horizontally (or vertically), it must always enter that square horizontally (or vertically).

Now, if the ant's path was periodic (and thus bounded), there would have to be a square that the ant visits repeatedly, but whose top and right neighbors the ant never visits during its periodic path. (To find such a square, just start from any square the ant is known to visit, and move up or right to adjacent visited squares as long as you can. Since the ant's path is, by assumption, bounded, this process will always terminate.) Thus, the ant must always either enter this square from the left and leave downwards, or enter it from below and leave left. But this means that the ant would have to always turn in the same direction after entering this square, which is impossible by definition.

share|cite|improve this answer

edited 5 hours ago

answered 9 hours ago

Ilmari KaronenIlmari Karonen

1,50188 silver badges1515 bronze badges

$endgroup$

add a comment | 

$begingroup$

The so-called Kohen–Kong theorem (described and attributed, without citation, to X.P. Kong and E.G.D. Kohen by Stewart (1994) (PDF); sometimes apparently misspelled as the "Kohen–Kung theorem") says that the path of Langton's ant can never be periodic (and, as a corollary, also cannot be bounded).

The proof is fairly simple, as the result follows directly from the following observations:

1. The path of the ant is (ultimately) periodic if and only if it is bounded. (Clearly, an unbounded path cannot be periodic. Conversely, if the ant would stay forever in a bounded region, there would be only a finite number of states in which the ant itself and the squares within that region could be, and therefore eventually the whole system would have to return to an earlier state.)


2. Since the ant turns 90° after every step, the direction from which it enters the next square alternates between horizontal and vertical. To return to a particular square after once leaving it, the ant must travel an even number of steps. Thus, if the ant once enters a given square horizontally (or vertically), it must always enter that square horizontally (or vertically).

Now, if the ant's path was periodic (and thus bounded), there would have to be a square that the ant visits repeatedly, but whose top and right neighbors the ant never visits during its periodic path. (To find such a square, just start from any square the ant is known to visit, and move up or right to adjacent visited squares as long as you can. Since the ant's path is, by assumption, bounded, this process will always terminate.) Thus, the ant must always either enter this square from the left and leave downwards, or enter it from below and leave left. But this means that the ant would have to always turn in the same direction after entering this square, which is impossible by definition.

share|cite|improve this answer

edited 5 hours ago

answered 9 hours ago

Ilmari KaronenIlmari Karonen

1,50188 silver badges1515 bronze badges

$endgroup$

share|cite|improve this answer

edited 5 hours ago

answered 9 hours ago

Ilmari KaronenIlmari Karonen

1,50188 silver badges1515 bronze badges

answered 9 hours ago

Ilmari KaronenIlmari Karonen

1,50188 silver badges1515 bronze badges

answered 9 hours ago

Ilmari KaronenIlmari Karonen

1,50188 silver badges1515 bronze badges